Recipe for a General, Powerful, Scalable Graph Transformer
Authors: Ladislav Rampasek
Mikhail Galkin
Vijay Prakash Dwivedi
Anh Tuan Luu
Guy Wolf
Dominique Beaini
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph transformers
graph neural networks
transformers
learning on graphs
graph representation learning

Abstract: We propose a recipe on how to build a general, powerful, scalable (GPS) graph Transformer with linear complexity and state-of-the-art results on a diverse set of benchmarks. Graph Transformers (GTs) have gained popularity in the field of graph representation learning with a variety of recent publications but they lack a common foundation about what constitutes a good positional or structural encoding, and what differentiates them. In this paper, we summarize the different types of encodings with a clearer definition and categorize them as being $\textit{local}$, $\textit{global}$ or $\textit{relative}$. The prior GTs are constrained to small graphs with a few hundred nodes, here we propose the first architecture with a complexity linear in the number of nodes and edges $O(N+E)$ by decoupling the local real-edge aggregation from the fully-connected Transformer. We argue that this decoupling does not negatively affect the expressivity, with our architecture being a universal function approximator on graphs. Our GPS recipe consists of choosing 3 main ingredients: (i) positional/structural encoding, (ii) local message-passing mechanism, and (iii) global attention mechanism. We provide a modular framework $\textit{GraphGPS}$ that supports multiple types of encodings and that provides efficiency and scalability both in small and large graphs. We test our architecture on 16 benchmarks and show highly competitive results in all of them, show-casing the empirical benefits gained by the modularity and the combination of different strategies.

Recipe for a General, Powerful, Scalable Graph Transformer
Ladislav Rampášek" Mila, Université de Montréal
Mikhaíl Galkin Mila, McGill University
Vijay Prakash Dwivedi
Anh Tuan Luu
Nanyang Technological University, Singapore
Nanyang Technological University, Singapore
Guy Wolf Mila, Université de Montréal
Dominique Beaini
Valence Discovery, Mila, Université de Montréal
Abstract
We propose a recipe on how to build a general, powerful, scalable (GPS) graph Transformer with linear complexity and state-of-the-art results diverse set benchmarks. Graph Transformers (GTs) have gained popularity the field graph representation learning with variety of recent publications but they lack common foundation about what constitutes good positional or structural encoding, and what differentiates them. In this paper, summarize the different types of encodings with a clearer definition and categorize them as being local, global relative. The prior GT's constrained to small graphs with few hundred nodes, here we propose the first architecture with a complexity linear in the number of nodes and edges O(N + E) by decoupling the local real-edge aggregation from the fully-connected Transformer. We argue that this decoupling does not negatively affect the expressivity, with our architecture being a universal function approximator on graphs. Our GPS recipe consists of choosing 3 main ingredients: (i) positional/strrucuuaal encoding, (ii) local message-passingg mechanism, and (iii) global attention mechanism. We provide a modular framework GRAPHGPS' that supports multiple types of encodings and that provides efficiency and scalability both in small and large graphs. We test our architecture on 16 benchmarks and show highly competitive results in all of them, show-casing the empirical benefits gained by the modularity and the combination of different strategies.
Introduction
Graph Transformers (GTs) alleviate fundamental limitations pertaining to the sparse message passing mechanism, c.g., over-smoothing [47], over-squashing [1], and expressiveness bounds [61, 45], by allowing nodes to attend to all other nodes in a graph (global attention). This benefits several real-world applications, such as modeling chemical interactions beyond the covalent bonds [63], or graph-based robotic control [37]. Global attention, however, requires nodes to be better identifiable within the graph and its substructures [14]. This has led to flurry of recently proposed fully- connected graph transformer models [14, 36, 63, 44, 31] as well as various positional encoding schemes leveraging spectral features [14, 36, 39] and graph features [16, 9]. Furthermore, standard
TTo whom correspondence should be addressed: ladislav rampaseicmmiaa.....m..aaaa.maaam quebec
'The source code of GRAPHGPS is available at: attps://gitann comm/aampasek/Graphdrss
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

global attention incurs quadratic computational costs O(N2) for a graph with N nodes and E edges, that limits GTs to small graphs with up to a few hundred nodes.
Whereas various GT models focus on particular node identifiability aspects, a principled framework for designing GT's is still missing. In this work, we address this gap and propose recipe for building general, powerful, and scalable (GPS) graph Transformers, The recipe defines (i) embedding modules responsible for aggregating positional encodings (PE) and structural encodings (SE) with the node, edge, and graph level input features; (ii) processing modules that employ a combination of local message passing and global attention layers (see Figure 1).
The embedding modules organize multiple proposed PE and SE schemes into local and global levels serving as additional node features whereas positional and structural relative features contribute to edge features. The processing modules define a computational graph that allows to balance between gressage-passing graph neural networks (MPNNs) and Transformer-like global attention, including attention mechanisms linear in the number of nodes (NN).
To the best of our knowledge, application of efficient attention models has not yet been thoroughly studied in the graph domain, e.g., only one work [1 I] explores the adaptation of Performer-style [12] attention approximation on small graphs. Particular challenges emerge with explicit edge features that are incorporated as attention bias in fully-commected graph transformers [36, 63]. Linear transformers do not materialize the attention matrix directly, hence incorporating edge features becomes non- trivial task. In this work, we hypothesize that explicit edge fcatures are not necessary for the global graph attention and adopt Performer [12] and BigBird [66] as exemplary linear attention mechanisms.
Our contributions are as follows. (i) Provide general, powerful, scalable (GPS) GT blueprint that incorporates positional and structural encodings with local message passing and global attention, visualized in Figure I. (ii) Provide a better definition of PEs and SEs and organize them into local, global, and relative categories. (iii) Show that GPS with linear global attention, e.g., provided by Performer [12] or BigBird [66], scales to graphs with several thousand nodes and demonstrates competitive results even without explicit edge features within the attention module, whereas existing fully- fully-connected GTs [36, 63] are limited to graphs of up to few hundred nodes. (iv) Conduct an extensive ablation study that evaluates contribution of PEs, local MPNN, and global attention components in perspective of several benchmarking datasets. (v) Finally, following the success of GraphGym [65] we implement the blueprint within modular and performant GRAPHGPS package.
2 Related Work
Graph Transformers (GT). Considering the great successes of Transformers in natural language processing (NLP) [55, 32] and recently also in computer vision [18, 25, 24], it is natural to study their applicability in the graph domain as well. Particularly, they are expected to help alleviate the problems of werr-soothing and over-squashing [1. 54] in MPNNs. which are analogous to the vanishing gradients and lack of long-term dependencies in NLP. Fully- conleceo Graph Transformer [14] was first introduced together with rudimentary utilisation of eigenvectors of the graph Laplacian as the node positional encoding (PE), to provide the otherwise graph-unawand Transformer a sense of nodes' location in the input graph. Building on top of this work, SAN [36] implemented an invariant aggregation of Laplacian's 's eigenvectors for the PE, alongside conditional attention for real and virtual edges of graph, which jointly yielded significant improvements. Concurrently, Graphormer [63, 51] proposed using pair-wise graph distances (or 3D distances) to define relative positional encodings, with outstanding success on large molecular benchmarks. Further, GraphiT [44] used relative PE derived from diffusion kernels to modulate the attention between nodes. Finally, GraphTraas Trans [31] proposed the first hybrid architecture, first using a stack of MPNN layers, before fully-connecting the graph. Since, the field has continued to propose alternative GTs: SAT [9]. EGT [29]. GRPE [48].
Positional and structural encodings. There have been many recent works on PE and SE, notably on Laplacian PE [14, 36, 3, 57, 391, shortest-path path-distance [38, 63], node degree centrality [63], kernel distance [44], randdnmnwaaa walk SE [16], structure-awe aware [9, 6, 5], and more. Some works also propose dedicated networks to learn the PE/SE from an initial encoding [36, 16, 39, 9I. To better understand the different PE/SE and the contribution of each work, we categorize them in Table and examine their effect in Section 3.2. In most cases, PE/SE are used as soft bias, meaning they are simply provided as input features. But in other cases, they can be used to direct the messages [3] or create bridges between distant nodes [35, 54].
2

---

Positional encodings (PE)
Structural encodings (SE)
Graph features
GPS layers
Local node features. Sum the
Local mude features Diagumal the walk
Nodes features concitennted the
MPAN
model acingg given
diggonal elements random walk
nelghtourhhod
Mes Global rode frutures, Expetvacions of the Laplactan & associated to the k-lowest non zoro eigervolues.
R., disg( (ID ()")
Transformer
connected
Globbll mude featuree. k-inows: eigeniatues of the Laplacinn Ag.
Global feutunn g are concatenated to the node Reauures
with
input
teatures.
L-yayers repeated, being the current layer's indea.
Retative
Relative incicating
Scolean
Edge features 8
differensar lacellylobul Shown beloww gradient elgenvectors Sigh.
relutivn
Residual connections the MPPN and Tronsformer
layers are omiited for dority.
MLPs mix the node/edge features with the PE and St.
MIP
MLP
...
MLPP
MLP
layer
Vith
S-nnng
GINE
2-layer MLP
GetedGCN
...
PNA
Any alobal
batch-norm
Transformer
10.28, 0.7...
Any vanabll Inout
Performer
batch-norm
batch-norm
DeepSet
BigBlrd
DeepSet
MLLP
SignNet
MLP
Crecatmation
DeepSet pernectors, sagmentation hondle sign ambiguity gigeweectos,
enouding they
graphes same range.
Mall-
Pricupa reghisemnd agorogttr
SigeNett sign-ttnatiant nutworkk will acapted to work with verying number fign ambiguous digervectors.
MLP is mulli-laeer percuptron
Soph seuneh
processes the encodings learn
Hod- bun
meoninghy ghul structure.
Edgi fuuturss
DeepSet allows work vorylng number sigerssllonn ues.
Choice of muliie rodide:
Figure I: Modular GPS graph Transformer, with examples of PE and SE. Task specific layers for node/graphledge-level predictions, such as pooling or output MLP, are omitted for simplicity.
Linear Transformers. The quadratic complexity of attention in the original Transformer archi- tecture [55] motivated the search for more efficient attention mechanisms that would scale linearly developed for language modeling tasks, e.g., Linformer [58], Reformer [34], Longformer [4], Performer [12], BigBird [66], and have a
with the sequence length. Most of such linear transformers
dedicated Long Range Arena benchmark [52] to study the limits of models against extremely long input sequences. Pyraformer [40] is an example of linear transformer for time series data, whereas S4 [23]
general signal processing approach that employs the state space model theory without the attention mechanism. In the graph domain, linear transformers are not well studied. Choromanski al. [11] are the first adapt Performer-style attention kernelization small graphs
Methods
In this work we provide general. powerful, scalable (GPS) architecture for graph Transformers. following our 3-part recipe presented in Figure 1. We begin by categorization of existing positional (PE) and structural encodings (SE), a necessary ingredient for graph Transformers. Next, we analyse how these encodings also increase expressive power of MPNNs. The increased expressivity thus provides double benefit to our hybrid MPNN+Transformee architecture, which we introduce in Section 3.3. Last but not least, we provide an extensible implementation of GPS in GRAPHGPS package, built on top of PyG [20] and GraphGym [65].
3.1 Modular positional and structural encodings
One of our contribution is to provide modular framework for PE/SE. It was shown in previous works that they are one of the most important factors in driving the performance of graph Transformers. Thus, better understanding and organization of the PE and SE will aid in building of more modular architecture and in guiding of the future research.
We propose to organize the PE and SE into 3 categories: local, global and relative in order to facilitate the integration within the pipeline and facilitate new research directions. They are presented visually in Figure with more details in Table Although PE and SE can appear similar to some

---

Table 1:
The proposed categorization of positional encodings (PE) and structural encodings (SE). Some encodings are assigned to multiple categories in order to show their multiple expected roles.
Encoding type
Description
Examples
Allow a node to know its position and role within a local cluster of nodes. Within cluster, the closer two nodes are to each other, the closer their local PE will be,
Sum each column of non-diagonal elements of the m-steps random walk matrix.
Local PE node features
Distance between a node and the centroid of a cluster con- taining the node.
such as the position of a word in sentence (not in the text).
Allow a node to know its global position within the graph.
Eigenvectors of the Adjacency. Laplacian [15, 36] distance matrices.
Global PR node features
Within a graph, the closer two nodes are.
SignNet [39] (includes aspects of relative PE and local SE).
the closer their global PE will be, such
Distance from the graph's 'ss centroid.
the position of a word in a text.
Unique identifier for each connected component of the graph.
Allow two nodes to understand their dis- tances directional relationships.
Pair-wise node distances [38, 3, 36, 63, 44] based on shortest-
paths, heat kernels, random-walks, Green's function, graph
Relative PE edge features
Edge embedding that is correlated to the distance given by any global or local PF,
gendesic, or any local/glohal PF.
Gradient of cigenvectors [3. 36] or any local/globul PE.
such the distance between two words.
PEG layer [57] with specific node-wise distances.
Boolean indicating if two nodes are the same cluster.
Degree of a node [63].
Allow a node to understand what sub-
Diagonal of the m-steps random-wall matrix [16].
Local SE node features
structures it is part of.
Time-derivative
the beat- diagonal (gives the degree
Given an SE of radius m. the more similar the m--hop subgraphs around two nodes
at t 0).
Enumerate or count predefined structures such as triangles.
are, the closer their local SE will be.
rings, etc. [6. 68).
Ricci curvature [54].
Provide the network with information
Global SE graph features
about the global structure of the graph.
Eigenvalues of the Adjacency or Luplacian matrices [36]. Graph properties: diameter, girth, number of connected com- ponents, # of nodes, # of edges, nodes-to-edges ratio.
The more similar two graphs are, the closer their global SE will be.
Allow two nodes to understand how much their structures differ.
Relative SE edge features
Pair wise distance, encoding, gradient of any local SE.
Edge embedding that is correlated to the
Boolean indicating if two nodes are in the same sub-structure [5] (similar to the gradient of sub-structure enumeration).
difference between any local SE
extent, they are different yet complementary. PE gives notion of distance, while SE gives notion of structural similarity. One can always infer certain notions of distance from large structures, or certain notions of structure from short distances, but this is not a trivial task, and the objective of providing PE and SE remains distinct, as discussed in the following subsections.
Despite presenting a variety of possible functions, focus our empirical evaluations on the global PE, relative PE and local SE since they are known to yield significant improvements. We leave the empirical evaluation of other encodings for future work.
Positional encodings (PE) are meant to provide an idea of the position in space of given node within the graph. Hence, when two nodes are close to each other within a graph or subgraph, their PE should also be close. common approach to compute the pair- wise distance between each pairs of nodes or their eigenvectors as proposed in [38, 63, 36, 57], but this is not compatible with linear Transformers as it requires to materialize the full attention matrix [12]. Instead, we want the PE to either be features of the nodes or real edges of the graph, thus a better fitting solution is to use the eigenvectors of the graph Laplacian or their gradicnt [15, 3, 36]. See Table I for more PE examples.
Structural encodings (SE) are meant to provide an embedding of the structure of graphs or subgraphs to help increase the expressivity and the generalizability of graph neural networks (GNN). Hence, when two nodes share similar subgraphs, or when two graphs are similar, their SE should also be close. Simple approaches are to identify pre-defined patterns in the graphs as one-hot encodings, but they require expert knowledge of graphs [6. 5]. Instead, using the diagonal of the m-steps random-walk matrix encodes richer information into each node [16], such as for odd mn it can indicate if a node is a part of an m-long cycle. Structural encodings can also be used to define the globul graph structure, for instance using the eigenvalues of the Laplacian, or as relative edge features to identify if nodes contained within the same clusters, with more examples in Table 1.

---

3.2 Why do we need PE and SE in MPNN?
As reviewed earlier, several recent GNNs make use of positional encodings (PE) and structural encodings (SF) as soft biases to improve the model expressivity (summarized Table 1), which also leads to better generalization. In this section, we present an examination of PE and SE by showing how message-passin passing networks, despite operating on the graph structure, remain blind to the information encapsulated by the PE and SE.
I-Weiseeile--Leman test (I-WL). is well known that standard MPNNs are as expressive as the 1-WL test, meaning that they fail to distinguish non-isomorphic graphs under a I-hop aggregation. We argue that the selected local, global and relative PE/SE allow MPNNs become more expressive than the 1-WL test, thus making them fundamentally more expressive at distinguishing between nodes and graphs. To this end, we study the following two types of graphs (Figure and Appendix C.I).
Circular Skip Link (CSL) graph. In a CSL graph-pair [46], we want to be able distinguish the two non-isomorphic graphs. Since the 1-WL algorithm produces the same color for every node in both graphs, also every MPNN will fail to distinguish them. However, using a global PE (e.g.. Laplacian PE [15]) assigns each node a unique initial color and makes the CSL graph-pair distinguishable. This demonstrates that an MPNN cannot leam such PE from the graph structure alone. Next, using a local SE (e.g., diagonals of m-steps random walk) can successfully capture the difference in the skip links of the two graphs [42], resulting in their different node coloring [16].
Sskip (11,2)
Sskip (11,3)
(a) Circular Skip Link graphs
Decalin molecule. In the bicyclic Decalin graph, Figures 2b and C.Ib, the node is isomorphic node b, and so is the node 1-WL coloring of the nodes, and analogously MPNN, would generate one color for the nodes a, b and another color for c, e. The same applies to the aforementioned local SE [16]. In case of link prediction, this causes potential links (a, d) and (b, d) to be indistinguishable [67]. Using a distance- based relative PE on the edges or an eigenvector- based global PE, however, would allow to differentiate the two links.
node d. A
(b) Decalin molecular graph
Figure 2: Example graphs with anonymous nodes with- out distinguishing features.
3.3 GPS layer: an MrnN+Transformer hybrid
In this section we introduce the GPS layer, which is a hybrid MPNN+Transformer layer. First we argue how it alleviates the limitation of closely related work. Next, we list the layer update equations which can be instantiated with a variety of MPNN and Transformer layers. Finally, we present its characteristics in terms of modularity, scalability and expressivity.
Preventing early smoothing. Why not use an architecture like GraphTrans [31] comprising of few layers of MPNNs before the Transformer? Since MPNNs are limited by problems of over-smoothing. over-squashing, and low expressivity against the WL test [1. 54), these layers could irreparably fail to keep some information in the early stage. Although they could make use of PE/SE or more expressive MPNNs [3, 16], they are still likely to lose information. An analogous 2-stage strategy was successful in computer vision [18, 24] thanks to the high expressivity of convolutional layers on grids, but do not expect it to achieve the same success on graphs due to the limitations message- paatggeepasing.....
Update function. At each layer, the features are updated by aggregating the output of an MPNN layer with that of a global attention layer, as shown in Figures and D.1, and described by the equations below. Note that the edge features are only passed to the MPNN layer, and that residual connections with batch normalization [30] are omitted for clarity. Both the MPNN and GlobalAtth layers are modular, i.e., MPNN can be any function that acts on a local neighborhood and GlobalAttn can be any fully-connected layer. computed as
X e+1 E
CPS (x', E A)
(1)
X+1 E
MPNN (x', E A),
(2)
x
GlobalAttn' (x*).
(3)
x
-MLP' (x++) x(11).
(4)
5

---

where A E RNXN, is the adjacency matrix of graph with N nodes and E edges; X E R N E e RFxd are the d,-dimensional node and edge features, respectively; MPNN and GlobalAttn' are instances of an MPNN with edge features and of global attention mechanism at the ε-th layer with their corresponding learnable parameters, respectively; MLP is 2-layer MI.P block.
Modularity is achieved by allowing drop-in replacement for number of module choices, including the initial PE/SE types, the networks that processes those PE/SE, the MPNN and global attention layers that constitute a GPS layer, and the final task-specific prediction head. Further, as research advances in different directions, GRAPHGPS allows to easily implement new PE/SE and other layers.
Scalability is achieved by allowing for a computational complexity linear in both the number of nodes and edges O(N E); excluding the potential precomputation step required for various PE, such as Laplacian cigen-decomposition. By restricting the PE/SE to real nodes and edges, and by excluding the edge features from the global attention layer, we can avoid materializing the full quadratic attention matrix. Therefore we can utilize a linear Transformer with ((N) complexity, while the complexity of an MPNN is O For sparse graphs such as molecular graphs. regular graphs, and knowledge graphs, the edges are practically proportional to the nodes E' = ((N), meaning the entire complexity can be considered linear in the number of nodes O(N). Empirically, even on small molecular graphs, our architecture reduces computation time compared to other GT models, e.g., a model of -6M parameters requires 196s per epoch on the ugbg-molpeed [27] dataset, compared to 883s for SAN [36] on the same GPU type.
Expressivity in terms of sub-structure identification and the Weisfeiler-LLeman (WL) test is achieved via providing a rich set of PE/SE, as proposed in various works 36, 16, 5, 6] and detailed in Section 3.1. Further, the Transformer allows to resolve the expressivity bottlenecks caused by over-smoothing [36] and over-squashing [1] by allowing information to spread across the graph via full-connectivity. Finally, in Section 3.4, we demonstrate that, given the right components, the proposed architecture does not lose edge information and is a universal function approximator on graphs.
3.4 Theoretical expressivity
In this section, we first diseuss how the MPNN layer allows to propagate edge and neighbor informa- tion on the nodes. Then, we show that the proposed model is a universal function approximator on graphs, similarly to the SAN architecture [36].
Preserving edge information in the Transformer layer. Most GTs do not fully utilize edge features of the input graph. The Graph Transformer [14], SAN [36] and Graphormer [63] only use edge features to condition the attention between a pair of nodes, that is, they influence the attention gating mechanism but not explicitly involved in updating of the node representations. GraphiT [44] does not consider edge features at all. Recent 2-step methods GraphTrans [31] and SAT [9] can use edge features in their first MPNN step, however this step is applied only once and typically includes several rounds of message passing. Therefore this latter approach may suffer from initial over- smoothing, k-hopp neighborhoods together with the respective edge features need to be represented in fixed-sizer node representation.
On the other hand, in GPS, interleaving one round of local neighborhood aggregation via an MPNN layer with global self-attention mechanism reduces the initial representation bottleneck and enables iterative local and global interactions. In the attention, the key-query-valuu mechanism only explicitly depends on the node features, but assuming efficient representation encoding by the MPNN, the node features can implicitly encode edge information, thus edges can play role in either the key, query, or values. In Appendix C.2, we give a more formal argument on how, following an MPNN layer, node features can encode edge features alongside information related to node-connectivity.
Universal function approximator on graphs. Kreuzer et al. [36][Sec. 3.5] demonstrated the universality of graph Transformers. It was shown that, given the full set of Laplacian eigenvectors, the model was universal function approximator on graphs and could provide an approximate solution to the isomorphism problem, making it more powerful than any Weisfeiler-Lenne test given enough parameters. Here, we argue that the same holds for our architecture since we can also use the full set of eigenvectors, and since all edge information can be propagated to the nodes.
(WL) isomorphism

---

Table Summary of the ablation studies. Details of the architectural choices, parameters, standard deviation, and computation times are presented in Appendix B.
(a) Ablation of the Transformer and MPNN layers. We observe a major drop when using only a Transformer without an MPNN. Further, most datasets henefit from using Transformer, without any negative impact.
(b) Ablation of the PE and SE: types. RWSE provides consistent gains at relatively low computational cost, while SignNet is the single best performing en-
coding. albeit at increased computational cost.
ZINC
POQM4M
CIFARIO
MalNet -Tiay
ZINC
PCQMAM
CIFARIO
MalNet -Tiny
Ablation
subset
Ablation
subset
MAE 4
MAE 4
Acc. f
Acc. t
MAE
MAE
Acc. f
Acc. t
Global
Attention
nOne
Tranerormer
0.070
0.070
0.1213
0.1159
72.31
69.95
92.23
93.50
none
RWSE
0.113
0.070
0.1355
0.1 159
71.96
71.49
92.77
92.64
Performer
0.071
0.1142
70.67
92.64
LapPE
0.116
0.1201
72.31
92.74
BigBird
0.071
0.1237
70.48
92.34
SignNerMur
0.090
0.1 158
71.74
92.57
DeepSes
0.079
0.1144
72.37
93.13
MPNN
nORE
GINE
0.217
0.070
0.3294
0.1284
68.86
71.11
92.27
73.90
0.161
0.1209
72.10
92.27
GatedGCN
0.086
0.1159
72.31
92.64
"Encddings color-coded by their positional or structural type.
PNA
0.070
0.1409
73.42
91.67
Experiments
We perform ablation studies on 4 datasets to evaluate the contribution of the message- massage-passing module, the global attention module, and the positional or structural encodings. Then, we evaluate GPS on diverse set of 11 benchmarking datasets, and show state-of-the-ar (SOTA) results many cases.
We test on datasets from different sources to ensure diversity, providing their detailed description in Appendix 1. From the Benchmarking GNNs [15], test the ZINC, PATTERN, CLUSTER, MNIST, CIFARIO 10. From the open graph benchmark (OGB) [27], we test on all graph-level datasets: ogbg-molhiv, agbg-molpcba. ogbg-code2, and ogbg-ppa, and from their large-scale challenge we test on the OGB-LSC PCQM4Mv2 [28]. Finally, we also select MalNet-Ting [21] with 5000 graphs, each of up to 5000 nodes, since the number of nodes provide scaling challenge for Transformers.
4.1 Ablation studies
In this section, we evaluate multiple options for the three main components of our architecture in order to gauge their contribution to predictive performance and to better guide dataset-specific hyper-parameter optimization. First, we quantify benefits of the considered global-attention modules in tasks. Then, note that the MPNN layer is essential part for fighhperforming models, and identify the layer type most likely to help. Finally, we observe when different global PE or local SE provide significant boost in the performance. All ablation results averaged over multiple random seeds and summarized in Table 2, with additional information available in Appendix B.
Global-Attention module. Here we consider global attention implemented O(N2) key-query- value Transformer attention or linear-time attention mechanisms of Performer or BigBird. We notice in Table 2a that using a Transformer is always beneficial, except for the ZINC dataset where changes are observed. This motivates our architecture and the hypothesis that long-range dependencies generally important. We further observe that Performer falls behind Transformer in terms of the predictive performance, although it provides a gain over the baseline and the ability to scale to very large graphs. Finally, BigB in setting offers significant gain, while also being slower than Performer (see Appendix B).
Having gain the ZINC dataset is expected since the task is combination of the computed octanol-water partition coefficient (cLogP) [60] and the synthetic accessibility score (SA-score) [19], both of which only count occurrences of local sub-structures. Hence, there is no need for global connectivity, but a strong need for structural encodings.
desssae-passing module. Next, we evaluate the effect of various message-passing architectures, Table 2a. is apparent that they are fundamental to the success of our method: removing the layer leads to significant drop in performance across all datasets. Indeed, without an MPNN, the edge
7

---

Table 3: Test performance five benchmarks from [15]. Shown is the mean s.d. of 10 runs with different random seeds. Highlighted are the top first, second, and third results.
ZINC
MNIST
CIFARIO
PATTERN
CLUSTER
Model
MAE
Accuracy 1
Accuracy
Accuracy
Accuracy 1
GCN [33]
0.367 = 0.011
90.705 = 0.218
55.710 + 0.381
71,892 0.334
08.49880.97
GIN [61]
0,526 = 0.051
96,485
0.252
55.255 : 1.527
85.387 = 0.136
64.716 1.553
GAT [56]
0,384 0.007
95.535
0.205
64.223 0.455
78.271 = 0.186
70.587 0.447
GatedGCN [7. 15]
0.282
97.340
0.143
6
85.568 + 0.088
=
GatedGCN-LSPE [16]
0.090 0.001
PNA [13]
0.188 + 0.004
0.11
70.35 à 0.63
DGN [3]
0.168 + 0.003
72.838 + 0.417
86.680 0.034
GSN [6]
0.101 # 0.010
CIN [5]
0.079 = 0.006
CRaWI [53]
0.085 0.004
97.944 + 0.050
69.013 0.259
GIN-AK+ [68]
0.080 = 0.001
72.19 = 0.13
86.850 0.057
SAN [36]
0.139 + 0.006
86.581 0.037
76.691 +: 0.65
Graphormer [63]
0.122 0.006
K- K-Subgraph SAT [9]
0.094 # 0.008
86.848 # 0.037
77.856 0.104
EGT [29]
0.108 # 0.009
98.173 + 0.087
68.702 4 0.409
86.821 # 0.020
79.232 0.348
GPS (ours)
0.070 # 0.004
98.051 +: 0.126 72.298 + 0.356
86.685 0.059
78.016 0.180
features are not taken into consideration at all. Additionally, without reinforcing of the local graph structure, the network can overfit to the PE/SE. This reiterates findings of Kreuzer et al. [36], where considerably larger weights were assigned to the local attention.
We also find that although vanilla PNA [13] generally outperforms GINE [26] and GatedGCN [7], adding the PE and SE results in major performance boost especially for the GatedGCN. This is consistent with results of Dwivedi al. [16] and shows the importance of these encodings for gating.
Perhaps the necessity of a local message- message-passing module is due to the limited amount of graph data, and scaling colossal datasets [49] that we encounter in language and vision could change that, Indeed, the Graphormer architecture [63] was able to perform very well on the full PCQM4My2 dataset without a local module. However, even large Transformer-based language models [8] and vision models [25] can benefit from an added local aggregation and outperform pure Transformers.
Positional/Structural Encodings. Finally, evaluate the effects of various PE/SE schemes, Table 2b. We find them generally beneficial to downstream tasks, in concordance to the vast literature on the subject (see Table 1). The benefits of the different encodings are very dataset dependant, with the random-walk structural encoding (RWSE) being more beneficial for molecular data and the Laplacian eigenvectors encodings (LapPE) being more beneficial in image superpixels. However, using SignNet with DeepSets encoding [39] as an improved way of processing the LapPE seems to be consistently successful across tasks. We hypothesize that SignNet can learn structural representation using the cigenvectors, for example, to generate local heat-kernels that approximate random walks [2]. Last but not least we evaluate PEG-layer design [57] with Laplacian eigenmap.
4.2 Benchmarking GPS
We compare GPS against a set of popular message-passing neural networks (GCN, GIN, GatedGCN, PNA, etc.), graph transformers (SAN, Graphormer, etc.), and other recent graph neural networks with SOTA results (CIN, CRaWI,, GIN-AK+, ExpC). To ensure diverse benchmarking tasks, we use datasets from Senchmarking-GNNY
[15], OGB [27] and its large-scale challenge [28], and Range Graph Benchmark [17]. with more details given in Appendix A.1. We report the mean and standard deviation over 10 random seeds if not explicitly stated otherwise.
Benchmarking GNNs [15]. We first benchmark our method on 5 tasks from Benchmarking GNNs [15], namely ZINC, MNIST, CIFAR10, 10, PATTERN, and CLUSTER, shown in Table 3. We observe that our GPS gives SOTA results on ZINC and the second best in 3 more datasets, showcasing the ability to perform very well variety of synthetic tasks designed test the model expressivity.
Open Graph Benchmark [27]. Next, we benchmark on all graph-level tasks from OGB, namely molhiy, molpcba. ppa, and code2, Table 4. On the molhiv dataset, observed our model to suffer
8

---

Table 4: Test performance in graph-level OGB benchmarks [27]. Shown the mean s.d. of 10 runs. Models that were first pre- pre-trained on another dataset or use an ensemble are not included here.
ogbg-molhiv
ogbg-molpcba
ogbg-ppa
ogbg-code2
Model
AUROC1 t
Avg. Precision f
Accuracy
Fl score
GCN+virtual node
0.7599 + 0.0119 0.7707 + 0.0149
0.2424 = 0.0034
0,6857 0.0061
0.1595 = 0.0018 0.1581 = 0.0026
GIN+virtual node
0.2703 = 0.0023
0.7037 = 0.0107
GatedGCN-LSPE
0.267 0.002
PNA
0.7905 0.0132
0.2838 = 0.003
0.1570 0.0032 0.0032
DeeperGCN
0.7858 + 0.0117
0,2781 = 0,0038
0.7712 = 0.0071
DGN
0,7970 + 0.0097
0.2885 # 0.0030
GSN (directional)
0.8039 0.0090
GSN (GIN+VN base)
0.7799 + 0.0100
CIN
0,8094 & 0.0057
GIN-AK+
0.7961 = 0.0119
0,2930 0.0044
CRaWi
0.2986 0.0025
ExpC [62]
0.7799 + 0.0082
0.2342 = 0.0029
0.7976 + 0.0072
SAN
0.7785 0.2470
0.2765 0.0042
GraphTrans (GCN-Virtual)
0.2761 0.0029
0.1830 0.0024
K-Subtree SAT
0.7522 0.0056
0.1937 = 0.0028
GPS (ours)
0.7880 0.0101
0.2907 0.0028
0.8015 0.0033
0.1894 0.0024
Table 5: Evaluation on PCQM4Mv2 [28] dataset. For GPS evaluation, we treated the validation set of the dataset as a test set, since the test-dev set labels are private. For more details refer to Appendix A.
PCQM4Mv2
Model
Test-dev MAE +
Validation MAE + Training MAE
# Param.
GCN
0.1398
0.1379
2.0M n/a
n/a
GCN-virtual
0.1152
0.1153
4.9M
GIN
0.1218
0.1195
n/a
3.8M
GIN-virtual
0.1084
0,1083
n/a
6.7M
GRPE [48]
0.0898
0.0890
n/a 46.2M
EGT [29]
0.0872
0.0869
n/a
89.3M
Graphormer [51]
n/a
0.0864
0.0348
48.3M
GPS-small
n/a
0.0938
0.0653
6.2M
GPS-medium
n/a
0.0858
0.0726
19.4M
from overfitting, but to still outperform SAN, while other graph Transformers do not report results. For the molpcba, ppa, and code2, GPS always ranks among the top 3 models, highlighting again the versatility and expressiveness of the GPS approach. Further, GPS outperforms every other GT on all 4 benchmarks, except SAT code2.
OGB-LSC PCQM4Mx2 [28]. The large-scale PCQM4Mv2 dataset has been a popular benchmark for recent GTs, particularly due to Graphormer [63] winning the initial challenge. We report the results in Table 5, observing significant improvements over message-passing networks at comparable parameter budget. GPS also outperforms GRPE [48] EGT [29], and Graphormer [63] with less than half their parameters, and with significantly less overfitting on the training set. Contrarily to Graphormer, do not need to precompute spatial distances from approximate 3D molecular conformers [64], the RWSES we utilize are graph-based only.
MalNet-Tiny. The Maiyet-Tiny [21] dataset consists of function call graphs with up to 5,000 nodes. These graphs are considerably larger than previously considered inductive graph-lcarning benchmarks, which enables to showcase scalability of GPS to much larger graphs than prior methods. Our GPS reaches 92.72% + 0.7pp test accuracy when using Performer global attention. Interestingly, using Transformer global attention leads to further improved GPS performance, 93.36% + 0.6pp (based on 10 runs), albeit at the cost of doubled run-time. both cases, we used comparable architecture to Freitas et al. [21], with 5 layers and 64 dimensional hidden node representation, and outperform their best GIN model with 90% accuracy. See Appendix B for GPS ablation study on MalNet-Tiny.
Long-Range Graph Benchmark [17]. Finally, we evaluate the GPS method on recent Long-Range Graph Benchmark (LRGB) suite of 5 datasets that are intended to test method's ability to capture rongerange dependencies in the input graphs. We abide to the -500k model parameter budget and

---

Table 6: Test performance on Long-range graph benchmarks (LRGB) [17].
Shown the mean + s.d. of
4 runs. The first, second, and third best are highlighted.
"SAN on COCO-SP exceeded 60h time limit on an NVidia A100 GPU system.
PascalVOC-SP
COCO-SP
Peptides-func Peptides-struct
PCQM-Contact
Model
score f
F1 score
AP1
MAE
MRR
GCN
0,1268 + 0.0060
0.0841 + 0.0010
0.5930 + 0.0023
0.3496 + 0.0013
0.3234 # 0.0006
GINE GatedGCN
0.1265 + 0.0076
0.1339 # 0.0044
0.5498
0.0079
0.3547 = 0.0045
0.3180 = 0.0027
0,2873 + 0.0219
0.2641 0.0045
0.5864 0.0077
0.3420 0.0013
0.3218 0.0011
GuledGCN+RWSE
0.2860 = 0.0085
0.2574 + 0.0034
0.6069 # 0.0035
0.3357 = 0.0006
0.3242 # 0.0008
Lrams
0.2694 + 0.0098
0.2618 = 0.0031
0.6326 0.0126
0.2529 + 0.0016
0.3174 0.0020
SAN+LapPE
0.3230 = 0.0039
0.2592 0,0158*
0.6384 0.0121
0.2683 = 0.0043
0.3350 0.0003
SAN+RWSE
0.3216 + 0.0027
0.2434 0.0156*
0.6439 # 0.0075
0.2545 + 0.0012
0,3341 # 0.0006
GPS (ours) 0.3748 + 0.0109
0.3412 0.0044
0.6535 0.0041
0.2500 + 0.0005
0.3337 0.0006
closely follow the experimental setup and hyperparameter choices of the graph Transformer baselines tested in LRGB [17]. We keep the same node/edge encoders and model depth (number of layers), deviating only in two aspects: i) we slightly decrease the size of hidden node representations to fit within the parameter budget, ii) we employ cosine learning rate schedule as in our other experiments (Section A.3). For each dataset utilize LapPE positional encodings and GPS with GatedGCN [7] and Transformer [55] components.
GPS improves over all evaluated baselines in 4 out of 5 LRGB datasets (Table 6). Additionally, we conducted GPS ablation studies on PascalVOC-SP and Peptides- fune datasets the same fashion as for 4 previous datasets in Table 2, presented in Tables B.5 and B.6, respectively. For both datasets the global attention, in form of Transformer or Performer, is shown to be a critical component of the GPS in outperforming MPNNs. In the case of PascalVOC-SP interestingly, the Laplacian PEs are not beneficial, as without them the GPS scores even higher Fl-score 0.3846, and PEG [57] relative distance embeddings enable the highest score of 0.3956.
5 Conclusion
Our work is setting the foundation for unified architecture of graph neural networks, with modular and scalable graph Transformers and a broader understanding of the role of graphs with positional and structural encodings. In our ablation studies, we demonstrated the importance of each module: the Transformer, flexible message- pesssage-passing. and rich positional and structural encodings all contributed to the success of GPS on wide variety of benchmarks. Indeed, considering 5 Benchmarking- GNNN tasks [15], 5 OGB(-LSC) tasks [27, 28), 5 LRGB tasks [17] and MalNet-Tiny, we outperformed every graph Transformer further showed that the model can scale to very large graphs of several thousand nodes, far beyond any previous graph Transformer. By open-soureing the GRAPHIPSS package, we hope accelerate the research in efficient and expressive graph Transformers, and move the field closer to a unified hybrid Transformer architecture for graphs.
11 out of 16 tasks while also achieving state-of-the-an on 8 of them. We
Limitations. We find that graph transformers are sensitive to hyperparameters and there is no one- size-fits-all all solution for all datasets. We also identify lack of challenging graph datasets necessitating long-range dependencies where linear attention architectures could exhibit all scalability benefits.
Societal Impact. As general graph representation learning method, we do not foresee imme- diate negative societal outcomes. However, its particular application, e.g., drug discovery or computational biology, will have to be thoroughly examined for trustworthiness or malicious usage.
Acknowledgments and Disclosure of Funding
This work was partially funded by IVADO (Institut de valorisation des données) grant 2RF-2019. 3583139727 and Canada CIFAR AI Chair [G. W.J. This research is supported by Nanyang Technolog- ical University, under SUG Grant (020724-00001) [V..D..] and Samsung Al graph at Mila [M...]. The content provided here is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.
10

---

References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
[2] Sebastian Andres, Jean- Donnninni Deuschel, and Martin Slowik. Heat kernel estimates for random walks with degenerate weights. Electronic Journal of Probabillit, 21:1-21, 2016.
[3] Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pages 748-758. PMLR, 2021.
[4] Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. CoRR, abs/2004.05 2020.
[5] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and Lehman go cellular: CW networks. Advances in Neural Information Processing Systems, 34:2625-2640, 2021.
[6] Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein, Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2022.
[7] Xavier Bresson and Thomas Laurent. Residual Gated Graph ConvNets. arX1v:1711.07553,
2017.
[8] Ivan Chelombiev, Daniel Justus, Douglas Orr, Anastasia Dietrich, Frithjof Gressmann, Alexan- dros Koliousis, and Carlo Luschi. Groupbert: Enhanced transformer architecture with efficient grouped structures. wrXiv:2106.05821 2021.
[9] Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-awart transformer for graph representation learning. Proceedings of the 39th International Conference on Machine Learning, 2022.
[10] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in Neural Information Processing Systems, 2019.
[11] Krzysztof Choromanski, Han Lin, Haoxian Chen, Tianyi Zhang, Arijit Sehanobish, Valerii Likhosherstov, Jack Holder, Tamas Sarlos, Adrian Weller, and Thomas Weingarten. From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked transformers. arXiv:2/07.07999 2021.
[12] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. In 9th International Conference on Learning Representations, 2021.
[13] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260- 13271, 2020.
[14] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv:2012.09699, 2020.
[15) Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv:2003.00 00982, 2020.
[16] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representationss 2022.
[17] Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Neural Information Processing Systems (NeurIPS 2022), Track on Datasets and Benchmarks, 2022.
[18] Stéphane d' Ascoli, Hugo Touvron, Matthew I. Leavitt, Ari S Morcos, Giulio Biroli, and Levent Sagun. Convit: Improving vision transformers with soft convolutional inductive biases. In International Conference on Machine Learning, pages 2286-2296 PMLR, 2021.

---

[19] Peter Ertl and Ansgar Schuffenhauer. Estimation of synthetic accessibility score of drug-like molecules based on molecular complexity and fragment contributions. Journal of cheminfor- maticy, 1(1):1-11, 2009.
[20] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with Py PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[21] Scott Freitas, Yuxiao Dong, Joshua Neil, and Duen Horng Chau. A large-scale database for graph representation learning. 35th Conference on Neural Information Processing Systems: Datasets and Benchmarks Track, 2021.
[22] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning,
pages 1263-1272. PMIR, R, 2017.
[23] Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022.
[24]
Jianyuan Guo, Kai Han, Han Wu, Chang Xu, Yehui Tang, Chunjing Xu, and Yunhe Wang. CMT: Convolutional neural networks meet vision transformers. arXiv:2107.06263 2021.
[25] Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang. An Xiao, Chunjing Xu, Yixing Xu, et al. A survey on vision transformer. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2022.
[26] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv: 1905. 2265,, 2019.
[27] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. 34th Conference on Neural Information Processing Systems, 2020.
[28]
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong. and Jure Leskovec. OGB- LSC: A large-scale challenge for machine learning on graphs. In 35th Conference on Neural Information Processing Systems: Datasets and Benchmarks Track, 2021.
[29] Md Shamim Hussain, Mohammed J Zaki, and Dharmashankar Subramanian. Global self- attention as a replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 655-665, 2022.
[30] Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448 118.456. PMLR, 2015.
[31] Paras Jain, Zhanghao Wu, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34, 2021.
[32] Katikapalli Subramanyam Kalyan, Ajit Rajasekharan, and Sivanesan Sangeetha. Ammus: A sur- vey of transformer-based pretrained models in natural language processing. 108.05228, 2021.
[33] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
2016.
[34] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer, In 8th International Conference on Learning Representations, 2020.
[35] loannis Koutis and Huong Le. Spectral modification of graphs for improved spectral clustering.
Advances in Neural Information Processing Systems, 32, 2019.
[36] Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Pruden- cio Tossou. Rethinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems, 2021.
[37] Vitaly Kurin, Maximilian Igl, Tim Rocktäschel, Wendelin Boehmer, and Shimon Whiteson. My body is a cage: the role of morphology in graph-based incompatible control. arXivv2010.01856, 2020.
[38] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 1444465-4475 2020.
12

---

[39] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv:2202. 13013, 2022.
[40] Shizhan Liu, Hang Yu, Cong Liao, Jianguo Li, Weiyao Lin, Alex X. Liu, and Schahram Dustdar. Pyraformer: Low-complexity pyramidal attention for long-range time series modeling and forecasting, In International Conference on Learning Representations, 2022.
[41] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representatiins, 2019.
[42] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020.
[43] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv: /905 / 2019.
[44] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT: Encoding graph structure in transformers. arXiv:2 (00:21006.0666.. 2021.
[45] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In The Third AAAI Conference on Artificial Intelligence, pages 4602-4609. AAAI Press, 2019.
[46] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning pages 4663-4673 PMLR, 2019.
[47] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations, 2020.
[48] Wonpyo Park, Woonggi Chang, Donggeon Lee, Juntae Kim, and Seung won Hwang. GRPE: Relative positional encoding for graph transformer. 1:Xix:2201111776
2022.
[49] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, (1(140):1-4 2020.
[50] Ryoma Sato. A survey on the expressive power of graph neural networks. arXtvv2003.04078. 2020.
[51] Yu Shi, Shuxin Zheng, Guolin Ke, Yifei Shen, Jiacheng You, Jiyan He, Shengjie Luo, Chang Liu, Di He, and Tie- Yan Liu. Benchmarking graphormer on large-scale molecular modeling datasets. arXiv:2203.00 048000 2022.
[52] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang. Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2021.
[53] Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Graph learning with Id convolutions on random walks. arXiv:2102.08786, 2021.
[54] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks graphs via curvature.
1rXiv22111.14522 2021.
[55] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
[56] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[57] Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representations, 2022.
[58] Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv:2006.0477 2020.
13

---

[59] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI. Series. 2(9):12-16, 16, 1968.
[60] Scott A Wildman and Gordon M Crippen. Prediction of physicochemical parameters by atomic contribations. Journal of chemical information and computer sciences, 39(5):68-887, 1999.
[61] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
[62] Mingqi Yang, Renjian Wang, Yanming Shen, Heng Qi. and Baocai Yin. Breaking the expression bottleneck of graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
[63] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems, 2021.
[64] Chengxuan Ying, Mingqi Yang. Shuxin Zheng, Guolin Ke, Shengjie Luo, Tianle Cai, Chenglin Wu, Yuxin Wang, Yanming Shen, and Di He. First place solution of KDD Cup 2021 & OGB large-scale challenge graph prediction track. (rXiv:2/660822/ 2021.
[65] Jiaxuan You, Rex Ying, and Jure Leskovee. Design space for graph neural networks. In Advances in Neural Information Processing Systems, 2020.
[66] Manzil Zaheer. Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big Bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems, 2020.
[67]
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances Neural Information Processing Systems, 34, 2021.
[68] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. International Conference on Learning Representations, 2022.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss limitations in Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 5
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We provide sketch in Section 3.4 and more details in Appendix C.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [Yes] Code, data, and instructions available in the supplementary material. We also include the performance traces/logs from our benchmarking experiments, supporting the results reported herein.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] We describe the datasets in Appendix A.I, splits in Appendix A.2, hyperparameters in Appendix A.3. Full configuration files are provided the supple- mentary material.
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We include standard deviations over several random seeds depending on the dataset evaluation protocol, more details are in Appendix A.2. (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] We elaborate on the compute and used resources in Appendix A.4.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] For datasets Appendix A. for software see Appendix A.4.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] The source code of GRAPHGPS is available in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] The used benchmarking datasets come from:
the molecular domain with no personal information, anonymized source code (ogbg- code2 and MalNet-Tiny), anonymized images (MNIST, CIFARI0), or are statistically generated.
5. If you used crowdsourcing 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]
15


Reviews:
[{"review_id": "gxzpCWCPgjI", "reviewer": "Reviewer_719v", "summary": "In this work, the authors propose a recipe on how to build a general, powerful, scalable  graph Transformer with linear complexity and state-of-the-art results on a diverse set of benchmarks.", "questions": "\n*  Many recent studies show that the dense attention map is not necessary in the Transformer. In graph Transformer, Do we really need to allow nodes to attend to all other nodes in a graph (global attenion).\n* The universal function on graph is not clear. A more detailed analysis why the proposed framework can achieve universal funtion approximator is required.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The proposed model is scalable due to its linear comlexity.\n\n2. The work considers lots of message:  positional and structural encodings with local message passing and global attention.\n\n3. The code is available and the performance of this work is good. \n\nWeaknesses:\n1. The overall algorithm can be well presented, like a presudo algorithm can be helpful to understand the implementation.\n\n2.   Many recent studies show that the dense attention map is not necessary in the Transformer. In graph Transformer, Do we really need to allow nodes to attend to all other nodes in a graph (global attenion).\n\n3. The universal function on graph is not clear. A more detailed analysis why the proposed framework can achieve universal funtion approximator is required.", "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": "Y7t6COO-OLv", "reviewer": "Reviewer_TX95", "summary": "This paper provides a general, powerful, scalable (GPS) graph Transformer with linear complexity. The authors redefine positional encodings (PEs) and structural encodings (SEs) with local, global, and relative categories and try to incorporate PEs and SEs with local and global attention in a graph Transformer. With the proposed GPS layers, the authors show the competitive result on several datasets. The proposed definition of PE and SE is general, and the paper has a good presentation of writing logic. However, I have several problems about the methods and experiments.", "questions": "refer to \"limitations\"", "limitations": "1. The PE and SE categories of local, global and relative are confusing. The local and global are opposite, but relative is another dimension, and it should be more suitable compared with the absolute PE.\n2. The description of relative SE is inconsistent with its example. The authors claimed that description allows two nodes to understand how much their structures differ, but examples are not enough to illustrate. Relative SE lacks support from related work, and this paper has no novelty on this point. Relative SE is more like a definition forcibly created to correspond to relative PE.\n3. The contribution of this paper is unclear. The first point should be merged with the third point, and the fifth point should not be regarded as the contribution of this paper. \n4. All methods in the paper are summary and induction, which lack novelty. There is no key innovation part of the paper.   \n5. The result of SAN on ogbg-molhiv dataset misses the decimal point and zero in Table 4.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The authors summarize the previous works about positional encodings and propose novel categories of structural encodings.\n2. The authors explain the rationality of definition and categories by the 1-Weisfeiler-Leman test and Circular Skip Link (CSL) graph.\n3. Based on PEs and SEs, the authors propose the GPS layer and present its characteristics with theoretical analysis. \n4. The paper has good writing and logical structure.", "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": "Cvvx24DrLMw", "reviewer": "Reviewer_Md1W", "summary": "The authors present a way how to efficiently use transformers on graph data. They report modular architecture, containing of graph positional encodings, structural encodings, and graph features, that further passed to an ensemble of arbitrary transformer block and arbitrary message passing neural network.", "questions": "How the model performs if we use another architecture instead of transformer block? Say simple MLP?", "limitations": "The authors addressed the potential societal impact and limitations in the collusion section.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper deals with an important and trending task. It's a nice and interesting read overall, the paper is technically sound, and well structured and describes the problem well. The authors provided performance testing on sufficient amount of datasets, and show the performance deviation with different random seeds. The authors provided a package built on top of graphGym which is a big plus.\n\nOn the other hand, the solid proof to use transformer block is missing. The authors claim that their solution has linear complexity, however from the table 2 is clear that linear attention block gives only marginal performance improvement, when for standard tasks (like LRA benchmark) linear transformers are on par, or even outperform vanilla transformer.", "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