Pure Transformers are Powerful Graph Learners
Authors: Jinwoo Kim
Dat Tien Nguyen
Seonwoo Min
Sungjun Cho
Moontae Lee
Honglak Lee
Seunghoon Hong
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph
transformer
self-attention
graph neural network
graph transformer
equivariant neural network
permutation equivariance
graph positional embedding

Abstract: We show that standard Transformers without graph-specific modifications can lead to promising results in graph learning both in theory and practice. Given a graph, we simply treat all nodes and edges as independent tokens, augment them with token embeddings, and feed them to a Transformer. With an appropriate choice of token embeddings, we prove that this approach is theoretically at least as expressive as an invariant graph network (2-IGN) composed of equivariant linear layers, which is already more expressive than all message-passing Graph Neural Networks (GNN). When trained on a large-scale graph dataset (PCQM4Mv2), our method coined Tokenized Graph Transformer (TokenGT) achieves significantly better results compared to GNN baselines and competitive results compared to Transformer variants with sophisticated graph-specific inductive bias. Our implementation is available at https://github.com/jw9730/tokengt.

Pure Transformers are Powerful Graph Learners
Jinwoo Kim Tien Dat Nguyen' Seonwoo Min Sungjun Cho?
Moontae Lee2.3
Honglak Lee²t Seunghoon Hong
KAIST PLG Al Research University of Illinois Chicago
Abstract
We show that standard Transformers without graph-specific modifications can lead to promising results in graph learning both in theory and practice. Given graph, we simply treat all nodes and edges as independent tokens, augment them with token embeddings, and feed them to a Transformer. With appropriate choice of token embeddings, we prove that this approach is theoretically at least as expressive as an invariant graph network (2-IGN) composed of equivariant linear layers, which is already more expressive than all message-passing Graph Neural Networks (GNN). When trained large-scale graph dataset (PCQM4Mv2), our method coined Tokenized Graph Transformer (TokenGT) achieves significantly better results compared to GNN baselines and competitive results compared to Transformer variants with sophisticated graph-specific inductive bias. Our implementation available htttt::// thub. hoon////77//ttoeng/
Introduction
In recent years, Transformer [68 has served versatile architecture in broad class of machine learning problems, such as natural language processing [17 77, computer vision [18), and reinforce- ment learning (9) to name few. It because the fully-attentional structure of Transformer is general and powerful enough to take, process, and relate inputs and outputs of arbitrary structures, eliminating need for data- and tasc-specific inductive bias be baked into the network architecture. Combined with large-scale training, it opens new chapter for building a versatile model that can solve a wide range of problems involving diverse data modalities and even a mixture of modalities 31 30 57
In graph learning domain, inspired by the breakthroughs, multiple works tried combining self- attention into graph neural network (GNN) architecture where message passing was previously dominant (50). As global self-attention across nodes cannot reflect the graph structure, however, these methods introduce graph-specific architectural modifications. This includes restricting self-attention to local neighborhoods [69 [51] 19), using global self-attention in conjunction with message-passing
34 and injecting edge information into global self-attention via attention bias [72 Despite decent performance, such modifications can be limiting constraint in terms of versatility, especially considering future integration to multi-task and multi-modal general-purpol attentional architectures [31. In addition, deviating from pure self lelf-attention, these methods may inherit the issues of pesssag--passing such as oversmoothing
GNN 55
43
78.22
29
54
52 and become incompatible with useful engineering techniques e.g., linear attention (65 developed for standard self-attention.
Instead, we explore the opposite direction of applying standard Transformer directly for graphs. For this, we treat all nodes and edges as independent tokens, augment them with appropriate token-wise embeddings, and feed the tokens input the standard Transformer: The model operates identically to Transformers used in language and vision; each node or edge is treated as a token, identical to the words in a sentence or patches of image [68 18]. Perhaps surprisingly, we show that this simple approach yields a powerful graph learner both in theory and practice.
Work done during internship LG AT Research.
i Equal corresponding authors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Tokenized Graph Transformer (TokenG'T)
Prediction
Transformer Encoder
Type Ideutifiers
[nade]] [odgel
1/2
24
Node Identifiors
arthxunrrual
U1
Node and Edge Tokens with Token-wise Embeeding
[grapb]
Input Graph
Overview of Tokenized Graph Transformer (TokenGT), We treat all nodes and edges of an input graph as independent tokens, augment them with orthonormal node identifiers and trainable type identifiers, and feed them standard Transformer encoder. For graph-level prediction, follow the common practice [7 [8] of using an extra trainable [graph] token.
Figure 1:
As key theoretical result, prove that with appropriate token-wise embeddings, self-attention over the node and edge tokens can approximate any permutation equivariant linear operator on graph [47] Remarkably, we show that very simple choice of embedding composed of node identifiers and type identifiers sufficient for accurate approximation. This provides solid theoretical guarantee that, with the embeddings and enough attention heads, Transformer is least expressive second-ordd order invariant graph network (2-IGN) [47] 344. which is already more expressive than all message- message-passing GNNs (21). This also immediately grants the model with the expressive power at least as good as the 2-dimensional Weisfeiler-Lehmae often sufficient for real-world graph data
(WL) graph isomorphism test [46], which is (33. We further extend our theoretical result hypergraphs with order-k hyperedges, showing that a Transformer with order-k generalized token embeddings is least expressive k-IGN and, consequently k-WL test.
We test our model, named Tokenized Graph Transformer (TokenGT), mainly on the PCQM4My2 large-scale quantum chemical property prediction dataset containing 3.7M molecular graphs (27). Even though TokenGT involves minimal graph-specific architectural modifications, significantly better than all GNN baselines, showing that the advantages of Transformer architecture combined with large-scale training surpass the benefit hard inductive bias of GNNs. Furthermore, TokenGT achieves competitive performance compared Transformer variants with strong graph- specific modifications [78] 29 54]. Finally, we demonstrate that TokenGT can naturally utilize efficient approximations in Transformers in contrast these variants, using kernel attention [1] that enables linear computation cost without much degradation in performance.
performs
2 Tokenized Graph Transformer (TokenGT)
In this section, we present the Tokenized Graph Transformer (TokenGTT), pure Transformer archi- tecture for graphs with token-wise embeddings composed of node identifiers and type identifiers (Figure T. Our goal in this section to provide a practical overview for theoretical analysis the architecture, we guide the readers to Section 3
Let G (V,E) an input graph with n nodes V == (UI...., Un and m edges E = {ei, ..., Cm S y2 associated with features X V E gaxC' and X E Immx respectively. We treat each node and edge as an independent token (thus (n + m) tokens total) and construct their features by X V X [(n+m)xCC A naïve way to process a graph is directly provide the tokens X as input to Transformer, but it is inappropriate as graph connectivity is discarded. To thoroughly represent graph structure, we augment
tokens X with token-wise embeddings, more specifically orthonormal node identifiers used for representing the connectivity of the tokens and trainable type identifiers that encode whether a token node or an edge. Despite the simplicity, we show that Transformer applied on these embeddings is theoretically powerful graph learner.

---

Node Identifiers The first component of token-wise embedding is the orthonormal node identifier that we use to represent the connectivity structure given in the input graph.
For given input graph 9 = (V,E), we first produce n node- orthonormal vectors P g R that we refer to as node identifiers. Then, we augment the tokens X with node identifiers follows.
For each node u E V, we augment the token X, as [ Pv. Pul. * For each edge (u, v) E &, we augment the token X (u.e) as [X (u,u): Poj.
Intuitively, Transformer operating the augmented tokens can fully recognize the connectivity structure of the graph since comparing the node identifiers between a pair of tokens reveals their incidence information. For instance, through dot-product (attention) since [Pu. u. P... PR,, Px] otherwise. This allows the Transformer to identify and exploit the connectivity structure of a graph, for instance by putting more weights on incident pairs when the local operation is important.
tell if an edge (u, v) is connected with node k 1 if and only if k E (u, v) and O
Notably, as the node identifiers are only required be orthonormal, we have a large degree of freedom in implementation choices. We outline two practical methods below as examples. Their implementation details can be found in Appendix A.3.
Orthogonal random features (ORFs), e.g., rows of random orthogonal matrix Q E R"*x obtained with QR decomposition of random Gaussian matrix G E R2
Laplacian eigenvectors obtained from eigendecomposition of graph Laplacian matrix, ie., rows of from A I-D 1/2 AD 1/2 1/2 D is degree matrix, and A, U correspond to cigenvalues and eigenvectors respectively (20].
U AU, where A " is adjacency matrix,
Among the two methods, node identifiers generated as ORFs do not encode any information about the graph structure as they are entirely random. This means the Transformer that operates on the ORF-based node identifiers needs to compile and recognize graph structure only from the incidence information provided by the node identifiers. Although this is challenging, perhaps surprisingly, we empirically show in Section 5 that Transformers are strong enough learn meaningful structural representations out of based node identifiers and outperform GNNs on large-scale task.
In contrast ORFs, Laplacian eigenvectors provide kind of graph positional embeddings (graph PEs) that describes the distance between nodes on a graph. Due to the positional information, yields better performance compared to ORFs in our experiments in Section One interesting aspect of Laplacian eigenvectors is that they can be viewed as a generalization of sinusoidal positional embeddings of NLP Transformers to graphs, cosine functions [20). Thus, by choosing Laplacian eigenvectors as node identifiers, our approach can be interpreted as a direct extension of the NLP Transformer for inputs involving relational structures.
the eigenvectors of 1D chain graphs are sine and
Type Identifiers The second component of token-wise embedding is the trainable type identifier that encodes whether a token is node edge. For given input graph G (V,E), we first prepare trainable parameter matrix E = E E E 2xd that contains two type identifiers EV and E for nodes and edges respectively. Then, we further augment the tokens with type identifiers as follows.
For each node v E V, we augment the token [x,, Pu, Po,P. Po. as X P. P. E
* For each edge (u, v) E, we augment the token [X (M.u): P P
X (u. P P.. ES].
These embeddings provide information on whether a given token is node or an edge, which is critical, e.g., when an attention head tries to attend specifically to node tokens and ignore edge tokens.
With node identifiers and type identifiers, obtain augmented token features X E (((++))((+24 which is further projected by trainable matrix whth E IR (C+2d, +d,)xa to be an input to Transformer. For graph-level prediction, we prepend a special token [graph] with trainable embedding X [graph] E RRd similar to BERT [17] and VIT (18). We utilize the feature of [graph] token at the output of the encoder as the graph representation, on which a linear prediction head is applied to produce the final graph-level prediction. Overall, the tokens z [X [graph]; (n) E [1+*+4m)xd are used as the input to the main encoder. As an encoder, we adopt the standard Transformer [68, which is an alternating stack of multihead self-attention layers (MSA) and feedforward MLP layers. We provide further details in Appendix A.I.I
Main Transformer
3

---

Inductive Bias Similar to Transformers in language and vision [8], Tokenized Graph Trans- former treats imput nodes and edges as independent tokens and applies self-attention them. This ap- proach leads to much less inductive bias than current GNNs, where the sparse graph structure, or more fundamentally, permutation symmetry of graphs is deliberately baked into each layer [21 47 46 34 For TokenGi,, such information is provided entirely as part of input using token-wiss embeddings, and the model has to learn how to interpret and utilize the information from data. Although such weak inductive bias might raise questions on the expressiveness of the model, our theoretical analysis in Section B shows that TokenGT is a powerful graph learner thanks to the token-wise embeddings and expressive power of self- atff-attetiinn For example, we show that TokenGT is more expressive than all message- meessag-passing GNNs under the framework of Gilmer et al. (2017) (1
3 Theoretical Analysis
We now present our theory. Our key result is that TokenGTT, standard Transformer with node and type identifiers presented in Section is provably least as expressive as the second-order Invariant Graph Network (2-IGN (47), which is built upon all possible permutation equivariant linear layers on a graph. This provides solid theoretical guarantees for TokenGT, such as being at least as powerful as the 2- graph isomorphism test and more expressive than all message-passing GNNs. Our theory based on a general framework on hypergraphs represented as higher-order tensors, which leads to the formulation of order-k TokenGT that is at least as expressive order-k IGN (k-IGN (47).
3.1 Preliminary: Permutation Symmetry and Invariant Graph Networks
Representing and Processing Sets and (Hyper)Graphs For set of n nodes, we often represent their features as X E R where X; E Rd is the feature of the i-th node. The set is unordered and, therefore, should be treated invariant to the renumbering of the nodes. Let S,, the symmetric group or the group of permutations I on [n] = n... By X we denote permuting rows of X with t, i.e., (T X); ;- X, (t)). Here, X and π X represent the identical set for all π E Sn.
Generally, we consider ghapes) represented as order-k tensor X E R= x with feature X, =
Xi E Rd attached (hyper)edge represented as multi-index i i= (i1 ..., ig) [n]**. Similar to sets, the tensor should be treated invariant to node renumbering by any E S, that acts on X by (T X); X (1) where (i) (x (x- (it),... x (i+)). That is, X and X represent the identical (hyper)graph for all æ. Due to such symmetry, to build a function F F(X) = for tensor X and target T, suitable way is to make them invariant F(rr X) = F(X) when the target is a vector or equivariant F(x X)
F(X) when the target is also tensor, for all X R xd and S,,.
In our theoretical analysis, we work on order-k dense tensor representation X RR* of a graph as they can represent node features (k- = 1), edge features (A= = 2), or hyperedge features (k >> 2) in a unified manner. This is interchangeable but slightly different from the sparse representation of a graph with edge set & used in Section 2 Nevertheless, in Section we empirically verify that our key theoretical findings work equally well for dense and sparse graphs
Invariant Graph Network We mainly develop our theoretical analysis upon Invariant Graph Networks (IGNs) 47 46), a family of expressive graph networks derived from the permutation symmetry of tensor representation of graphs. Here we provide a summary. In general, we define:
Definition 1. An order-k Invariant Graph Network (k-IGN) is a function Fg. R x - R written as the following:
Fx = MLP Lk- L .o.............................. 00 L
[
where each 1k is equivariant linear layer [47] from R xn is activation function, and Ta- is a invariant linear layer from T xdr to TR.
A body of previous work have shown appealing theoretical properties of k-IGN, including universal approximation [48 and alignment to &-Weisfeiler-Lehmman (k-WL) graph isomorphism test [46] 10 In particular, it is known that k-IGNs are theoretically at least as powerful as the k- test [46] It is
also known that 2-IGNs are already more expressive 47 34 than all message-passing GNNs under the framework of Gilmer et al. (2017) 211.

---

The core building block of IGN is invariant and equivariant linear layers 47 with maximal expres siveness while respecting node permutation symmetry. The layers are defined as follows:
Definition 2. An equivariant linear layer is a function Lk- : R xd + R" xd' written as follows for order-k input X E IR" xd.
(x)1(X)
Xj Σ Ofbx
B
where E [m]'.j E [ni] are multi-indices, Wp E RRdxd by E R. are weight and bias parameters, and B E Th and C² E Th' are binary basis tensors corresponding to order-(1 + k) and order-l equivalence classes μ and X, respectively. Invariant linear layer a special case of Lg->1 with
We provide the definition of the equivalence classes and basis tensors in Appendix A..I.. For now, is sufficient to know that the basis tensors are binary tensors that form the orthogonal basis of the full space of linear equivariant layers. In general, in Eq. 2 it is known that there exists bell(k + I) number of basis tensors B for the weight and bell(() number of basis tensors CAA for the bias.
3.2
Can Self-Attention Approximate Equivariant Basis?
Now, we present an intuition that connects Transformer (Section 2 and equivariant linear layer (Defi- For that, we write out the multihead self-attention layer follows:
nition 2
Xwx (X
MSA(X);= Ea Xiuh wh where a softmax
(3)
vdu
where H is number of heads, du is head size, and wh w Rdxdv, w/ E RRaxd wh E &Rdexd. xd
Our intuition is that the weighted sum of values with self-attention matrix a in Eq. 3 is analogous to the masked sum with basis tensor B in Eq. (2) up to normalization. This naturally leads to the following question: for a given equivariant layer Lic+ 18n xx gnn xd can we use Transformer layer with multihead self-attention MSA RB- xd' + Nxx with N n² to accurately approximate Lb-*k by having H = bell(2k) attention heads approximate each equivariant basis B"?
We show that this can be possible, but only if we provide appropriate auxiliary information to input. For example, let us consider first-order layer ---1- The layer has bell = basis tensors B I and 8 11 I for the weight, and bell(1)
basis tensor CA for the bias. Given an input set X E Rad it computes the following with w1, w2 Rddd b R.4:
(x-1(X) IXw1 + (11 I)Xu2 + 16b
(4)
Now consider approximating basis tensor B = I with an attention matrix a The approximation accurate when i-th query always only attends to i-th key and ignores the rest. To achieve the attention structure consistently, Le.. agnostic to input X, we need to provide auxiliary input that self-attention can "latch onto" to faithfully approximate a' x I. Without this, attention must entirely rely on the inputs X, which is unreliable and can lead to approximation failure, e.g., when X has repeated rows.
For the auxiliary information, we prepare n mise orthonormal vectors P E Radd (note that this is identical to node identifiers in Section 2 and augment the input to X = [ P] E R (d+dp). Let us assume that the query and key projections in Eq. (3) ignore X and only leave P scaled by vā with a > 0. Then attention matrix is computed as a softmax(S) where S, = aP, P,. Here, due to the orthonormality of P, we have P.T. P, = 1 only if j and otherwise 0, which leads to = aI. With a + oo by scaling up the query and key projection weights, the softmax becomes arbitrarily close to the hardmax operator, and we obtain the following:
(5) Thus, self-attention utilize the auxiliary information P achieve an input-agnostic approximation
a² = softmax(al) + as a + 0o.
of a to I. Notably, we can achieve similar approximation for 8 11 using the same P by flipping the sign of keys, which gives a = softmax(- -II due to orthonormality. By sending co, now attention from the i-th query to the i-th key is suppressed, and obtain the following:
1
2 = softmax (-al) + n
T
I) as a + co.
(6)
5

---

Note that this approximation is accurate only up to row normalization as rows of a² always sum to one due to softmax, while B = 11 I binary. In our proofs of the theoretical results, we perform appropriate denormalization with MLP after MSA achieve an accurate approximation.
Overall, we see that simple auxiliary input P suffices for two attention heads to approximate the equivariant basis of L1-1 accurately. We now question the following. Given appropriate auxiliary information as input, can a Transformer layer with b2l) attention heads accurately approximate LK by having each head approximate each equivariant basis B What would be the sufficient auxiliary input? We answer the question by showing that, with (order-k generalized) node and type Transformer layers accurately approximate equivariant layers TE-sk via input-agnostic head-wise approximation of each equivariant basis.
identifiers presented in Section 2
3.3 Pure Transformers are Powerful Graph Learners
We now present our main theoretical results that extend the discussions in Section 3.2 to any order k. Note that h: corresponds TokenGT for graphs presented in Section 2 extend TokenGT to hypergraphs. All proofs can be found in Appendix A.I
With 2, we naturally
We first introduce generalized node and type identifiers (Section 2 for order-k tensors X E IR"xxd We define the node identifier P E Raxdy as an orthonormal matrix with n rows, and the type identifier trainable matrix E Rhell(k)xdde that contains bell(A) rows E
E E>ha((k), each of which is designated for an order-k equivalence class y. Then, we augment each entry of input tensor as [X. ....... Pi,: E? where (f1,..., ix) E
Let us exemplify. For A = 1 (sets), each i-th entry is augmented as [X P,, E. consistent with our discussion in Section 3.2 For k = 2 (graphs), each (i, i)-th entry is augmented as [X;, P,, P, E and each jith entry (i + j) is augmented as [Xij, P., Pj, ETa]. This is consistent with TokenGT in Section 2 which augments nodes with E" = E and edges with E = E
With node and type identifiers, we obtain augmented order-k tensor X E "R" (d) We use a trainable projection ntn E (d++Ad, +dd x to map them to hidden dimension dy of Transformer. We now show that self- self-attention on X" can accurately approximate equivariant basis:
Lemma 1.
For all X E 1B=='xe xd and their augmentation Xtn, relf-attention coefficients a (Eq.
computed with X "n can approximate any basis tensor B E IR= of order-k equivariant linear layer Lk-k (Definition 2) to arbitrary precision up normalization.
Consequently, with the node and type identifiers. a collection of bell(2k) attention heads can approxi- mate the collection of all basis tensors of order-k equivariant layer. This leads to the following:
Theorem 1. For all X E B² xd and their augmentation Xin, a Transformer layer with (2k) self-attention heads that operates on X"" can approximate an order-k equivariant linear layer (X) (Definition 2 to arbitrary precision.
While the approximation in Lemma iis only accurate up to normalization softmax normalization, for the approximation in Theorem T we perform appropriate denormalization using MLP after multihead self-attention and can obtain an accurate approximation.
inputs (keys) due to
By extending the result to multiple layers, we arrive at the following:
Theorem 2. For all X E BRn xd and their augmentation Xin, a Transformer composed Tf layers that operates Xin followed by sum-pooling and MLP can approximate k-IGN Fg(X) (Defiittion) 7 to arbitrary precision.
This directly leads to the following corollary:
Corollary 1. Transformer on node and type identifiers in Theorem is least as expressive as k-IGN composed of order-k equivariant linear layers.
Corollary aallows us to draw previous theoretical results the expressiveness of k-IGN 46 47 and use them to lower-bound the provable expressiveness of a standard Transformer:
Corollary 2. A Transformer on node and type identifiers in Theorem 2 is at least powerfal as k- graph isomorphism test and is more expressive than all cessuage-psssing GNNs within the framework of Gilmer et al. (2017) (21)

---

4
Related Work
We outline relevant work including equivariant neural networks, theory on expressive power of Transformers and their connection to modeling equivariance, and Transformers for graphs.
Equivariant Neural Networks A machine learning task is often invariant or equivariant to specific symmetry of imput data, e.g., image classification invariant the translation of an input image. A large body of literature advocated baking the invariance or equivariance into neural network as type of inductive bias (e.g.. translation equivariance of image convolution), showing that it reduces the number of parameters and improves generalization for wide range of learning tasks involving
various geometric structures [13 14 73
[3)] Ravanbakhsh et al. (2017) [56] showed that any equivariant layer for discrete group actions is equivalent to specific parameter
66
49
53 60
sharing structure. Zaheer et al. (2017) [2) and Maron et al. (2019) 47 derived the parameter sharing for node permutation-symmeet equivariant linear layers and k-IGN in Section 3.1 The work on equivariant neural networks underlic our theory of how a standard Transformer can be a powerful learner for sets and (hyper)graphs.
data (sets and (hyper)graphs), which gives the maximally expressive
Expressive Power of Transformers and Its Connection to Equivariance Recent work involving Transformers often focus on minimizing the domain- and task-specific inductive bias and scaling the model and data so that any useful computation structure can be learned [18] 31
30
7 9 39]. The
success of this approach is, to some degree, attributed the high expressive power of Transformers that allows learning diverse functions suited for the data at hand [8] 39
3 4 .1 Recent theory has
shown that Transformers are expressive enough to even model certain equivariant functions [[] 39]
Andreoli et al. (2019) [1] cast self-attention and convolution into a unified framework using basis tensors similar to ones in Section 3.T Cordonnier et al. (2020) [55 advanced the idea and showed that Transformers with relative positional encodings can approximate any image convolution layers. Lee et al. (2019) [39] and Kim et al. (2021) (34) showed that Transformers can model equivariant linear layers for sets [82, which can be viewed as the first-order case of our theory (see Section (.2)) To our knowledge, our work is the first to show that standard Transformers are expressive enough to provably model maximally expressive equivariant layers and k-IGN for (hyper)graphs with k 2.
Transformers for Graphs Unlike in language and vision, developing Transformers for graphs challenging due to (1) the presence of edge connectivity and (2) the absence of canonical node ordering that prevents adopting simple positional encodings (50). To incorporate the connectivity
of edges, early methods restricted self-attention to local neighborhoods (thus reducing to message- passing) [19] 55 69) or used global self-attention with auxiliary message-passing modules (58 [3
As message- passing suffers from limited expressive power [77] and oversmoothing [40, 8 52), recent
works often discard them and use global self-attention on nodes with heuristic modifications to process edges 778 (29 (5 38 (2). Ying et al. (2021) (78) proposed to inject edge encoding based on shortest paths through self-attention bias. Kreuzer et al. (2021) 38) proposed to incorporate edges into self-attention matrix via elementwise multiplication. On the contrary, we leave the self-attention unmodified and provide both nodes and edges with certain token-wise embeddings (Section 2 as its input. To incorporate graph structure into nodes, on the other hand, some approaches focus on developing graph positional encoding, e.g., based on Laplacian eigenvectors (20
42 38 While
these can be directly incorporated into our work via auxiliary node identifiers for better performance, leave this as future work. We further note that current graph Transformers that utilize Laplacian
positional encoding rely heavily on heuristic edge encoding (29 38 while ours does not. Another closely related approach is the Higher-order Transformer (34 which generalizes k-IGN with masked self-attention. While it is highly complex to implement due to hard-coded head-wise equivariant masks, our method can be implemented efforteeslly using any available implementation of standard Transformer. Furthermore, our method is more flexible as the model can choose to use different attention heads focus on specific equivariant operator (e.g., local propagation) if needed. We further discuss the difficulty in applying linear attention to graph Transformers in Appendix A.2
5 Experiments
We first conduct synthetic experiment that directly confirms our key claims in Lemma T (Section Then, empirically explore the capability of Tokenized Graph Transformer (TokenGT) (Section using the PCQM4My2 large-scale quantum chemistry regression dataset (27). We further present experiments transductive node classification datasets involving large graphs in Appendix A.4.3
7

---

Table 1: Second-order equivariant basis approximation, We report average and standard deviation of L2 eπror averaged over heads over runs. For Random/ORF (first-order), we sample random embeddings independently for each token.
dense input
sparse input
node id.
type id.
train L2 g
Test L2
train L2
Test L21
47.95 0.600
53.93 1.426
29.88 0.450
34.70
1.167
32.38 = 0.448
40.06 + 1.202
15.92 = 0.275
20.39 0.765
Random (first-oddrr)
32.19 = 0.476
32.49 + 3.687
15.87 = 0.247
16.56 0.904
ORF (frst-order)
32.35 = 0.369
39.87 +: 1.263
13.87 1: 0.247
16.56 0.908
Random
5,909 0.019
5.548 0.090
8.152 0.042
8.270
0.285
ORF
5.472 0.035
5.143 0.078
7.167 0.025
7.190 0.217
Laplacian eigenvector
1.899 3.050
1.702
2.912
0.288
0.019
0.064
0.010
Random
0.375 = 0.009
0.234 1 0.011
0.990 + 0.108
0.875
0.042
ORF
0.080 = 0.001
0.009 + 5c-5
0.129 + 0.002
0.011 0.002
Laplacian eigenvector
0.053 + 1.5e-5
0.005 1 1e-4
0.101 0.003
0.019 0.007
embedding
Type only
Node only
type Equivariant
0006
0004
0006
0002
0,000
Self-attention matrix
Basis tensor
Figure 2: Self-attention maps learned under various node and type identifier configurations for two target equivariant basis tensors (out of 15). For better visualization, we clamp the entries by 0.01. Self-attention learns acute patterns coherent to equivariant basis when orthonormal node identifiers and type identifiers are both provided as input. More images can be found in Appendix A.4.
5.1 Approximating Second-Orde Equivariant Basis
As in Theorem ! and (Section 3). our argument on the expressive power of TokenGT relies on
its capability to approximate order-k permutation equivariant linear layers LE- (Definition 2 Specifically, I Lemma I states that such capability depends on the ability of each self-attention head
a¹ " (Eq. (3) accurately approximate each equivariant basis B ..... (eanca) (Definition) 2 up to normalization.
We verify this claim for k = 2 (second-order; graphs) in a synthetic setup using Barabási-Albert random graphs. We use a multihead self-attention layer (Eq. (3) with bell + 2) = 15 heads and explicitly supervise head-wise attention scores " to approximate each (normalized) equivariant basis tensor 8 by minimizing I.2 loss. Having the layer hyperparameters fixed, we provide different combinations of node and type identifiers, and test multihead self-attention can jointly approximate all 15 equivariant basis on unseen graphs. We experiment with both dense and sparse graph representations: for graphs with n nodes and m edges, the dense graph considers all n² pair- wise edges input in Section 3 whereas the sparse graph considers only the present edges as in Section 2 Further details can be found in Appendix A.3.2
We outline the results in Table I Consistent with Lemma] I self-attention achieves accurate approxi- mation equivariant basis only when both the orthonormal node identifiers and type identifiers are given. Here, Laplacian eigenvectors (Lap, O) often yield slightly better results than orthogonal ran- dom features (ORF, O) presumably due to less stochasticity. Interestingly, we see that ellfaattnttoon transfers the learned daeeudo-Jequivarte self-attention structure to unseen graphs near perfectly.

---

Table 2: Results on PCQM4Mv2 large-scale graph regression benchmark. We report the Mean
Absolute Error (MAE) on the validation set, and report MAE the unavailable test set if possible.
method
parameters
valid MAE
MAE asympiotics
Message-passing GNNs
GCN (27
2.0M
0.1379
0.13998
O + m
GIN 22
3.8M
0.1195
0.1218
O(n + m)
GAT
6.7M
0.1302
N/A
Oln + m7)
GCN-VN
4.9M
0.1153
0.1152
O + m
GIN-VK
27
6.7M
0.1083
0.1084
O(n + m)
GAT-VN
6.7M
0.1192
N/A
O + 174
GN (large)
55.2M
0.1361
O(n + m7)
Transformers with strong graph-specific modifications
Graphormer 63
48.33 3M
0.0864
N/A
O(n O(ne) O(n))
EGT 29
89.3M
0.0869
0.0872
GRPE S54
46.2M
0.0890
0.0898
Pure Transformers
Transformer
48.5M
0.2340
NIA
Oi(n + m]
TokenGT (ORF)
48.6M
0.0962
NIA 0.0919
( + m)
TokenGT (Lap)
48.5M
0.0910
( + m))
TokenGi (Lap) Performer
48.5M
On + m)
TokenGT (ORF)
TokenGT (Lap)
Mean attention distance (hops)
Mean attention distance (hops)
Head
Head
Head 32
Head 32
Network depth (layer)
Network depth (layer)
Figure 3: Attention distance by head and network depth. Each dot shows mean attention distance in hops across graphs of head a layer. The visualization is inspired by Dosovitskiy et al. (2020) [8] More images can be found in Appendix A.4.2
Non-orthogonal random embeddings lead to inaccurate approximation (Random, O), highlighting the importance of orthogonality of node identifiers. The approximation is also inaccurate when we sample ORF P, independently for each token t (ORF (first-order), Q) instead of using concatenated node identifiers [P.., P..] for token (u, r). This supports our argument in Section 2 that the incidence information implicitly provided via node identifiers plays a key role in approximation.
In Figure 2 we provide a visualization of self-attention maps learned under various node and type identifier choices. Additional results can be found in Appendix A.4.I
5.2 Large-Scale Graph Learning
An exclusive characteristic of TokenGT its minimal graph-specifis inductive bias, which requires to learn internal computation structure largely from data. As such models are commonly known to work well with large-scale data 688 18, we explore the capability of TokenGT on the PCQM4Mv2 quantum chemistry regression dataset 27 one of the current largest with 3.7M molecular graphs.
For TokenGT, we use both node and type identifiers, and use main Transformer encoder config- uration based on Graphormer (78) with 12 layers, 768 hidden dimension, and 32 attention heads. We try both ORF and Laplacian eigenvector as node identifiers, and denote corresponding mod- els as TokenGT (ORF) and TokenGT (Lap) respectively. As an ablation, we also experiment with the same Transformer without node and type identifiers, which we denote as Transformer. Finally, we apply the kernel attention [II] that approximates the attention computation to linear cost (TokenGT (Lap) + Performer). We use AdamW optimizer with (3,, 32) = (0.99, 0.999) and weight decay 0. and 60k learning rate warmup steps followed by linear decay over 1M iteration with batch size 1024. For fine-tuning, we use 1 warmup, O. 1M training steps, and cosine learning rate decay. We train the models on 8 RTX 3090 GPUs for 3 days. Further details are in Appendix A.3.3

---

We provide the results in Table 2 A standard Transformer on the node and edge tokens cannot recognize graph structure and shows low performance (0.2340 valid MAE). Yet, the picture changes as soon as we augment the tokens with node and type identifiers. Notably. TokenGT (ORF) achieves 0.0962 MAE, which is already better than all GNN baselines. This is a somewhat surprising result, as both ORF and the Transformer are not aware of graph structures. This implies Transformer is strong enough to learn to interpret and reason over the incidence structure of tokens provided only implicitly by the node and type identifiers. By further switching to Laplacian eigenvectors that encode position on graphs [20], we observe a performance boost to 0.0910 MAE, competitive to Transformers with sophisticated graph-specific modifications (e.g., shortest path-based spatial encoding (78). While such methods inject graph structure into attention matrix via bias term and therefore strictly require O cost, TokenGT enables adopting kemnlizattio for pure self-attention [T]] resulting in TokenGT (Lap) + Performer with the best performance among (n + m) models (0.0935 MAE). Further discussion the empirical performance of TokenGT can be found in Appendix A.5
While our theory in Section guarantees that TokenGT can reduce to an equivariant layer by learning fixed equivariant basis at each attention head, in practice, it can freely utilize multihead self-attention to learn less restricted and more useful computation structure from data. To analyze such a structure, we compute the attention distance across heads and network depth by averaging pairwise token distances on a graph weighted by their attention scores (Figure 3). This distance is analogous to the number of hops in message-passing. passing. In both TokenGT (ORF) and TokenGT (Lap), in the lowest layers, some heads attend globally over the graph while others consistently have small receptive fields (acting like local message- paagggggganinggggee operator). In deeper layers, the attention distances increase, and most heads attend globally. Interestingly, this behavior is highly consistent with Vision Transformers on image patches [18. suggesting that hybrid architectures based on convolution to aid VIT [16 30 might also work well for graphs. While TokenGT (ORF) shows relatively consistent attention distance over heads, TokenGT (Lap) shows higher variance, implying that learns more diverse attention patterns. Judging from the higher performance of TokenGT (Lap), this suggests that the graph structure information of the Laplacian eigenvector facilitates learning useful and diverse attention structures, which calls for future exploration of better node identifiers based on graph PEs [8 42
6 Conclusion
We showed that Transformers directly applied to graphs can work well in both theory and practice. In the theoretical aspect, we proved that with appropriate token-wiss embeddings, Transformer on node and edge tokens is at least as expressive as k-IGN and k-WL test, making it more expressive than all message-passing GNNs. For such token-wise emheddings, we showed that a combination of simple orthonormal node identifiers and trainable type identifiers suffices, which we also verified with a synthetic experiment. In an experiment with PCQM4My2 large-scale dataset, we show that Tokenized Graph Transformer (TokenGT) performs significantly better than all GNNs and is competitive with
Transformer variants with strong graph-specific architectural components 78 29 54
While the results suggest promising research direction, there are challenges to be addressed in future work. First, treating each node and edge tokens requires O((n + m) asymptotic cost due to the quadratic nature of self- self-attention. While we address this to some degree with kernelization and achieve On + m) cost, other types of efficient Transformers (e.g.. sparse) that can deliver better performance are left to be tested. Another issue is slightly lower performance compared to the state- of-the-art. Adopting Transformer engineering techniques from vision and language domains, such as data scaling 77] 18) deepening 70 /7). hybrid architectures [6 80 and self-supervision 17 244,
are promising. In the societal aspect, to prevent the potential risky behavior in, e.g. decision making from graph-structured inputs, interpretability research regarding sellf-ttention on graphs is desired.
We finish with interesting research directions that stem from our work. As our approach advocates viewing a graph as (n + m) tokens (37], it opens up new paradigms of graph learning, including au- toregressive decoding, in-context learning, prompting, and multimodal learning. Another interesting direction is to extend our theory and use self-attention to approximate equivariant basis for general discrete group actions, which might be viable approach for learning equivariance from data.
This work was supported in part by Institute of Information communications Technology Planning & Eyaluation (ITTP) (No. 2022-0-00926, 2022-0-00959, 2021 1021-0002068, and 2019-0-00075) and the National Research Foundation of Korea (NRF) (No. 2021R1 RIICC110125400 grants funded by the Korea government (MSIT).
Acknowledgement
10

---

References
[1] J.-M. Andreali. Convolution, attention and structure embedding. arXiv, 2019. (Cited on
[2] A.-I.. Barabasi and R. Albert. Emergence of scaling in random networks. arXiv, 1999. (Cited TO)
[3] S. Bhattamishra, A. Patel, and N. Goyal. On the computational power of transformers and its implications
in sequence modeling. In CoNLL, 2020. (Cited on 7
[4] S. Bhojanapalli, C. Yun, A. S. Rawat, attention models. In ICML, 2020. (Cited on
Reddi, and S. Kumar. Low-rank bottleneck multi-head
[5] S. Brody. U. Alon, and E. Yahav. How attentive are graph attention networks? In ICLR, 2022. (Cited on
[6] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond cuclidean data, IEEE Signal Process. Mag., 2017. (Cited on
[7] T. B. Brown, Mann, N. Ryder, M. Subbiah, Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry,
A. Askell, S. Agarwal, A. Herbert- Voss, 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, I. Sutskever, and D. Amodei. Language models few-shot learners. In
NeurIPS, 2020. (Cited on 7 [0]
[8] C. Cai and Y. Wang. A note over-smoothing for graph neural networks. arXiv, 2020. (Cited on
[9] L. Chen, K. Lu. A. Rajeswaran, Lee, A. Grover, M. Laskin, Abbeel. A. Srinivas, and I. Mordatch. Decision transformer: Reinforcement learning via sequence modeling. In NewrIPS, 2021. (Cited on [
[10] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructurcs? In NeurIPS, 2020. (Cited on !
[11] K. M. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlós, P. Hawkins, J. Q. Davis, A. Mohiuddin, I., Kaiser, D. B. Belanger, J. Colwell, and A. Weller. Rethinking attention with performers.
In ICLR, 2021. (Cited 2 10 11
[12] K. M. Choromanski, M. Rowland, and A. Weller. The unreasonable effectiveness of structured random orthogonal embeddings. In NeurlPS, 2017. (Cited 10
[13] T. Cohen and M. Welling. Group equivariant convolutional networks. In ICML, 2016. (Cited on
[14] T. Cohen and M. Welling. Steerable cnns. In ICLR, 2017. (Cited on
[15] Cordonnier, A. Loukas, and Jaggi. On relationship between self-attention and convolutional layers. In ICLR, 2020. (Cited on (
[16] Z. Dai, H. Liu, Q. V. Lc, and M. Tan. Coatnet: Marrying convolution and attention for all data sizes. In NeurIPS, 2021. (Cited on 10
[17] J. Devlin, M. Chang, K. Lee, and K. Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In NAACI-HIT, 2019. (Cited on α
TO
[18] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenbom,, X. Zhai, T. Unterthiner, M. Dehghani, M. Min- derer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x16 words: Transformers for image recognition al scale. In ICLR, 2021. (Cited on
10
[19] V. Dwivedi and Bresson. generalization of transformer networks to graphs. arXiv, 2020. (Cited on
[20] V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. arXiv, 2020. (Cited on 7
[21] J. Gilmer, S. S. Schoenholz, F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017. (Cited on 2
[22] A. N. Gorban, Y. Tyukin, D. V. Prokhorov, and Sofeikov. Approximation with random bases: Pro contra. Inf. Sci., 2016. (Cited on [4)
[23] B. Hanin and M. Sellke. Approximating continuous functions by relu nets of minimal width. arXiv, 2017. (Cited on [
[24] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. B. Girshick. Masked autoencoders are scalable vision learners. arXiv, 2021. (Cited on 10)
[25] D. Hendrycks and K. Gimpel. Gaussian error linear units (gelus). arXiv, 2018. (Cited on
[26] K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks universal approximators. Neural Networks, 1989, (Cited on 7)
[27] W. Hu, M. Fey, H. Ren, M. Nakata, Y. Dong, and J. Leskovec, OGB-LSC: A large-scale challenge for machine learning on graphs. arXiv, 2021. (Cited on

---

[28] G. Huang, Y. Sun. Z. Liu. Sedra, and K. Q. Weinberger. Deep networks with stochastic depth. In ECCV,
2016. (Cited on IT
[29] M. S. Hussain, M. J. Zaki, and D. Subramanian. Edge-aus augmented graph transformers: Global self-attention
is enough for graphs. arXiv, 2021. (Cited on
T0
[30] A. Jaegle, S. Borgeaud, J. Alayrac, C. Doersch, C. lonescu. D. Ding. S. Koppula, D. Zoran, A. Brock,
E. Shelhamer, O. Hénaff, M. M. Botvinick, A. Zisserman, O. Vinyals, and Carreira. Perceiver 10: general architecture for structured inputs & outputs. arXiv, 2021. (Cited on I
[31] A. Jacgle, F. Gimeno, A. Brock, O. Vinyals, A. Zisserman, and J. Carreira. Perceiver: General perception with iterative attention. In ICML,, 2021. (Cited on [ 7
[32] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In ICML, 2020. (Cited on())
[33] N. Keriven and G. Peyré. Universal invariant and cquivariant graph neural networks, In NeurIPS, 2019. (Cited on [5]
[34] J. Kim, S. Oh, and S. Hong. Transformers generalize deepsets and can be extended to graphs and hypergraphs. In NeurlPS, 2021. (Cited
6 [5]
[35] D. Kingma and J. Ba. Adam: method for stochastic optimization. In ICLR, 2015. (Cited on 14
[36] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks, In ICLR,
2017. (Cited on 14
[37] Z. Kolter, S. Bai, D. Wilmott, M. Kornbluth, and J. Mailoa. First place solution of 2019 champs pre- dicting molecular properties challenge. httpps//www. kaggle. wttp///coooccccceeeeeeeeeeeeaaee scalar--------- coupling/ Eiscussiin/106575 2019. (Cited on TT)
[38] D. Kreuzer, D. Beaini, W. Hamilton, V. Létourneau, and P. Tossou, Rethinking graph transformers with spectral attention. NewrIPS, 2021. (Cited on T0 9
14p
[39] J. Lee. Y. Lee. J. Kim, A. R. Kosiorek, S. Choi, and Y. W. Teh. Set transformer: A framework for neural networks. In ICML, 2019. (Cited on
attention-
permutation-invarii
[40] Q. Li, Z. Han, and X. Wu. Deeper insights into graph convolutional networks for semi- supissupe learning. In AAAI, 2018. (Cited [
[41] V. Likhosherstov, K. Choromanski, and A. Weller. On expressive power of self-attention matrices. arXiv, 2021. (Cited o
[42] D. Lim, J. Robinson, L. Zhao, E. Smidt, S. Sra, H. Maron, and S. Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv, 2022. (Cited 10 [4]
[43] K. Lin, L. Wang, and Z. Liu. Mesh graphormer. In ICCV, 2021. (Cited on
[44] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In ICLR, 2019. (Cited on
[45] X. Ma, X. Kong. S. Wang, C. Zhou, J. May, H. Ma, and Zettlemoyer. Luna: Linear unified nested
attention. NewrIPS, 2021. (Cited on
[46] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. In NeurlPS. 2019. (Cited on
15)
[47] H. Maron, H. Ben Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In ICLR, 2019. (Cited on 2
4
6 (5)
[48] H. Maron. Fetaya, N. Segol, and Lipman. On the universality of invariant networks. In JCML, 2019.
(Cited on 4 [5]
[49] H. Maron, O. Litany, G. Chechik, and E. Fetaya. On learning sets of symmetric elements. In ICML, 2020. (Cited on
[50] E. Min, R. Chen, Y. Bian, T. Xu, K. Zhao, W. Huang, P. Zhao, J. Huang, S. Ananiadou, and Y. Rong. Transformer for graphs: An overview from architecture perspective. arXiv, 2022. (Cited on [
[51] D. Q. Nguyen, T. D. Nguyen, and D. Phung. Universal graph transformer self-attention networks. In
www, 2022. (Cited on [7
[52] K. Oono and T. Suzuki. Graph neural networks exponentially lose expressive power for node classification.
In ICLR, 2020. (Cited on
[53] H. Pan and R. Kondor. Permutation equivariant layers for higher order interactions. In AISTATS, 2022. (Cited on 7
[54] W. Park, W. Chang, D. Lee, J. Kim, and S. won Hwang. Grpe: Relative positional encoding for graph transformer. arXiv, 2022. (Cited on I 7 L0)
[55] H. Peng, N. Pappas. D. Yogatama, R. Schwartz, N. A. Smith, and L. Kong. Random feature attention. In ICLR, 2021. (Cited on
12

---

[56] S. Ravanbakhsh, J. G. Schneider, and B. Póczos. Equivariance through parameter-sharing. In ICML, 2017.
(Cited on 7
[57] S. Reed, K. Zolna, E. Parisotto, S. G. Colmenarejo, A, Novikov, G. Barth-Maron, M. Giménez, Sulsky,
J. Kay, J. 'T. Springenberg, T. Eccles, J. Bruce, A. Razavi, A. Edwards, N. Heess, Y. Chen, R. Hadsell,
O. Vinyals, M. Bordbar, and N. de Freitas. A generalist agent. arXiv, 2022. (Cited on
[58] Y. Rong, Y. Bian, T. Xu, W. Xie, Y. Wei, W. Huang, and J. Huang. Sclf-supervised graph transformer on large-scale molecular data. In NewrlPS, 2020. (Cited on
[59] B. Rozemberczki, C. Allen, and R. Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 2021. (Cited on 13
[60] H. Serviansky, N. Segol, J. Shlomi, K. Cranmer, E, Gross, H. Maron, and Y. Lipman. Set2graph: Learning graphs from sets. In NeurlPS, 2020. (Cited on (5)
[61] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of graph neural network evaluation. arXiv, 2018. (Cited on [3)
[62] Z. Shen, M. Zhang, H. Zhao, S. Yi. and H. Li. Efficient attention: Attention with linear complexities. In WACV, 2021. (Cited onl)
[63] Y. Shi, Zheng, G. Ke, Y. Shen, J. You, He, S. Luo, C. Liu, D. He, and T. Liu. Benchmarking graphormer on large-scale molecular modeling datasets. arXiv, 2022. (Cited on 2
[64] A. Steiner, A. Kolesnikov, X. Zhai, R. Wightman. J. Uszkoreit, and L. Beyer. How to train your vit? data,
augmentation, and regularization in vision transformers. arXiv, 2021. (Cited on [T]
[65] Y. Tay, M. Dehghani, D. Bahri, and D. Metzler. Efficient transformers: A survey, arXiv, 2020. (Cited on I
[66] N. Thomas. T. E. Smidt, S. Kearnes, L. Yang, L. Li, K. Kohlhoff, and P. Riley. Tensor field networks: Rotation- and vanslation-cquuivaiaat neural networks for 3d point clouds. arXiv, 2018. (Cited on 7
[67] Tompson. R. Goroshin, A. Jain, LeCun, and C. Bregler. Efficient object localization using convolutional networks. In CVPR, 2015. (Cited on [0]
[68] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, I. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In NeurlPS, 2017. (Cited
[69] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. In ICLR, 2018. (Cited on о 14
[70] H. Wang. S. Ma, L. Dong, Huang, D. Zhang, and F. Wei. Deepnet: Scaling transformers to 1, 0.00 layers.
arXiv, 2022. (Cited on 10}
[71] S. Wang, B. Z. Li, M. Khabsa, H. Fang, and H. Ma. Linformer: Self-attention with lincar complexity. arXiv. 2020. (Cited on
[72] X. Wang, Z. Tu, Wang, and S. Shi. Self-attention with structural position representations. EMNLP- IJCNPP, 2019. (Cited []
[73] M. Weiler, M. Geiger, M. Welling, W. Boomsma, and T. Cohen. 3d steerable cnns: Learning rotationally
equivariant features in volumetric data. In NeurlPS, 2018 (Cited 7
[74] N. Wies, Y. Levine, D. Jannai, and A. Shashua. Which transformer architecture fits my data? A vocabulary bottleneck in self-attention. In JCML, 2021. (Cited on [0]
[75] R. Xiong. Y. Yang. D. He, K. Zheng. S. Zheng. C. Xing, H. Zhang, Y. Lan, L. Wang. and T. Liu. On layer
normalization in the transformer architecture. In ICMI., 2020. (Cited on [T]
[76] Y. Xiong, Z. Zeng, R. Chakraborty, M. Tan, G. Fung, Y. Li, and V. Singh. Nyströmformer: A nyström-based algorithm for approximating self-attention. In AAAI, 2021. (Cited (n
[77] K. Xu, W. Hu, J. Leskovee, and S. Jegelka. How powerful are graph neural networks? In ICT.R, 2019. (Cited on 7 14
[78] C. Ying. T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T. Liu. Do transformers really perform bad for graph representation? In NeurIPS, 2021. (Cited on
10 14p
[79] F. X. Yu, A. T. Suresh, K. M. Choromanski, D. N. Holtmann- and S. Kumar. Orthogonal random features. In NeurlPS, 2016. (Cited on [
[80] K. Yuan, S. Guo, Z. Liu, A. Zhou, F. Yu, and W. Wu. Incorporating convolution designs into visual transformers. ICCV, 2021, (Cited on 10
[81] C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar, Are transformers universal approximators of sequence- to to-uuunecc functions? In ICLR, 2020. (Cited on α
[82] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Póczos, R. Salakhutdinov, and A. J. Smola. Deep sets. In NeurIPS, 2017. (Cited o
[83] M. Zopf. 1-w1 expressiveness is (almost) all you need. arXiv, 2022. (Cited on 2
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] . You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section 3 and Section 5
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 6
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3
(b) Did you include complete proofs of all theoretical results? [Yes] We include them in the supplementary file.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as a URL)? [Yes] We include them in the supplementary file.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] See Section
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 5.2
(b) Did you mention the license of the assets? [Yes] See Section 5.2
(c) Did you include any new assets either in the supplemental material as URL? [Yes] We include them in the supplementary file.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're
using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "lVmW25iPI5Y", "reviewer": "Reviewer_To3r", "summary": "This paper proposes a variant of graph transformers, the Soft Graph Transformer (SGT). In particular, all nodes and edges are simply treated as independent tokens, and then they are augmented with token embedding. The authors prove this approach is theoretically at least as expressive as an invariant graph network, which is already more expressive than all message-passing graph neural networks. SGT performs significantly better than all GNNs and is competitive with Transformer variants with strong graph-specific architectural components.", "questions": "I have no questions.", "limitations": "The authors have addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe motivation is clear. This paper proposes an approach of applying a standard Transformer directly for graphs. Although the algorithm is simple, it is shown that this simple approach yields a powerful graph learner in terms of both theory and experiment. The theoretical analysis is comprehensive and proves the effectiveness of the proposed method.\n\nWeaknesses:\nThe experiments are not very convincing. Only one graph dataset, PCQM4Mv2, is considered in the paper. If one to two new datasets are added, that would be great. It will be better to conduct more experimental ablation studies, such as the effects of type embedding. The results seem not strong enough, and more experiments can make this paper stronger.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "Sz-hv6eoMtl", "reviewer": "Reviewer_YAnt", "summary": "The paper proposes a new way to encode nodes and edges on the graph so that one can directly transform the input graph into a sequence and directly use the sequence transformers. With carefully designed position, type encodings, the paper proves that it is theoretically as expressive as a second-order invariant graph network. The authors validate several of their claims through a synthetic experiment and an experiment on real-world dataset PCQM4M. It achieves comparable performance with prior models and has the potential to scale to large graphs since the proposed method can just do a drop-in replacement of the transformer with all efficient transformer architectures.", "questions": "- How do you set the dimension of node identifiers? Is the dimension the number of nodes in the graph? How do you deal with a batch of graphs with different sizes?\n- Is there any difference between modeling directed and undirected edges? If one edge (u,v) is undirected, I think the modeling of (u,v) and (v,u) should be identical. However, it seems that the edge embedding will be $[\\mathbf{X}_{(u,v)}, \\mathbf{P}_u, \\mathbf{P}_v]$ for (u,v) and $[\\mathbf{X}_{(u,v)}, mathbf{P}_v, \\mathbf{P}_u]$ for (v,u). \n- Also wonder how does the above issue about directedness and undirectedness generalize to higher-order hypergraphs?\n- It’s interesting that using Laplacian eigenvectors as node identifiers and not using type id leads to comparable performance with using type identifiers on sparse inputs (the 7th row vs the final three rows in Table 1). Any insights?\n- Have you submitted your final results to get the numbers on the test set of PCQM4M? The authors do not seem to include a discussion on how they tune the hyperparameters on PCQM4M especially since you only have the validation set. The validation performance alone is not convincing enough, let alone the proposed method achieves higher MAE than prior transformer-based methods such as Graphormer. \n- The model achieves higher MAE than all the three graph transformer baselines in Table 2. I did not find sufficient discussion on this result. There is basically a one-liner, which still emphasizes that the proposed method can be optimized computationally while not discussing the reasons for not matching the same empirical performance. State-of-the-art results are not necessary for publication but detailed discussion and analysis on why not is necessary.\n- Can the proposed method be applied to other node-level or edge-level tasks like link prediction?\n- The authors mentioned in the checklist that they included the code and data. However, their supplementary is only a PDF, I do not see the code to reproduce the concrete numbers listed in the experiment section.\n", "limitations": "The only limitation in my mind is that the proposed method may not necessarily generalize to large graphs as well as message passing networks. Although the paper mentioned that they can use all the efficient transformer architectures, yet there are no experiments, no evidence showing this. The full transformer architecture with quadratic complexity still runs. Besides, it would be nice to add more discussion on how the proposed method may be applied to other node and edge level tasks (as raised in the above section).", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper aims to serialize graphs so that we can leverage the benefits of all those expressive transformer architectures which have been investigated for the past few years. Although I’m not entirely sure that the prior graph transformers cannot leverage different attention/transformer architecture. I think the challenge of applying transformers to graphs is always how to differentiate nodes (i.e., designing different position encodings) while preserving the permutation invariance and equivariance. I like the second part of the paper where the model with the proposed position encodings is proved to be as expressive as a 2-IGN, and I also enjoy the first experiment which validates the theoretical claim.\n\nOne weakness/question in mind is on scalability and how to adapt to graphs with various sizes. The node identifier matrix $\\mathbf{P} \\in \\mathbb{R}^{n \\times d_p}$, where $d_p$ should be at least $n$. How can this scale to large graphs? Also the position encoding dimensions (node + type identifiers) may be much larger than the original node/edge features ($\\mathbf{X}_v$).\nLaplacian eigenvectors as node identifiers are still different from sinusoidal positional embeddings in NLP since the sinusoidal position embeddings can be of arbitrary dimension, but for the Laplacian eigenvectors, the dimension is fixed (which is the number of nodes on the graph).\n\nBesides, from a practitioner point of view, the experimental results are not sufficient. The authors only evaluate their model on one real world dataset PCQM4M. There are multiple graph classification/regression dataset on Open Graph Benchmark and Benchmarking GNNs. Even on the PCQM4M dataset, it seems that all variants of the proposed methods are worse than prior graph transformers. Even with the claim that the proposed method can leverage efficient transformer implementations, it does not really address my concern. 1. you never show that the model actually works in a setting where we really need an efficient implementation, i.e., other quadratic implementations do not run or oom. 2. why can’t the prior works use the same efficient transformer implementations?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EByE1osL5uL", "reviewer": "Reviewer_E51P", "summary": "The authors of the paper claim that Transformers can be as expressive as graph-invariant networks by applying them directly to a graph and treating all nodes and edges in the graph as tokens. Using appropriate node and type identifiers, self-attention can approximate any permutation equivariant linear operator in the graph. Orthogonal random features and Laplacian feature vectors for node identifiers are proposed. The final proposed model, Soft Graph Transformer (SGT), achieves performance improvements over the GNN baseline on the PCQM4Mv2 dataset.", "questions": "1. Are node and type identifiers learned?", "limitations": "1. Evaluate on only one graph dataset.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. It is novel to treat nodes and edges as input tokens to Transformers and add node and type identifiers.\n2. It is shown that SGT is as expressive as 2-IGN with equivariant linear layers.\n\nWeakness: \n1. Evaluate on only one graph dataset.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5eDd0-MG5X", "reviewer": "Reviewer_pDDE", "summary": "The authors show that we can use the vanilla Transformers for languages and Vit without any graph-specific modifications can lead to promising results in graph learning. The interesting view is that the proposed model Soft Graph Transformer (SGT) uses edge features as tokens compared to other graph learners who only use node features as input tokens. And identifiers are designed to encode the graph's local information. Therefore, they can use the techniques for Transformers without any other modifications. Furthermore, they also theoretically proved their equivalence to the k-IGN models and the k-WL algorithms. However, I think their empirical evaluations are not enough and the advantages of their proposed SGT are not clear compared with other Graph Transformers.", "questions": "Questions:\n\n1. I'd like to know whether other baselines like GraphFormers use the Laplacian positional embedding or not. Since the Laplacian positional embeddings are useful tricks and have been used in GraphFormers, SAN and other works.\n\n2. I'd like to know why SGT performs worse than other GraphFormers. Do you have any possible causes?", "limitations": "I think they should clearly tell the readers that they are not the first who uses the Laplacian's eigenvectors in Graph Transformers since this trick is a simple but effective one.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Proposed a new view on the tokens instead of only using node features.\n2. They also give a theoretical analysis of SGT's representative ability as powerful as k-WL and more expressive than GCN. Their analysis also gives us a direct reason why the node identifiers are orthogonal.\n\nWeaknesses:\n1. It is still not clear to me why Transformers for graph need to be the same as other transformers. I think it is natural that Graph Transformers need to have something special for graph tasks. According to \"No free lunch\" theorem, there can not be an algorithm that works the best for all tasks. Therefore, considering task-specific models are necessary. For example, Swin-Transformers takes the inductive bias for vision tasks into Transformers for vision tasks.\n\n2. The empirical results also show no advantages compared with other Transformers for Graphs with larger resources cost. As for SGT+Performer, I'm not sure whether such a comparison is fair since other Transformers for Graphs may also use the linearized acceleration by modifying their models like Linformer's attention?\n\n\nTypo:\nline 286 Figure 1 -> Figure 2", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept