Attending to Graph Transformers
Authors: Luis Müller
Mikhail Galkin
Christopher Morris
Ladislav Rampášek
Venue: Accepted by TMLR ()

Abstract: Recently, transformer architectures for graphs emerged as an alternative to established techniques for machine learning with graphs, such as (message-passing) graph neural networks. So far, they have shown promising empirical results, e.g., on molecular prediction datasets, often attributed to their ability to circumvent graph neural networks’ shortcomings, such as over-smoothing and over-squashing. Here, we derive a taxonomy of graph transformer architectures, bringing some order to this emerging field. We overview their theoretical properties, survey structural and positional encodings, and discuss extensions for important graph classes, e.g., 3D molecular graphs. Empirically, we probe how well graph transformers can recover various graph properties, how well they can deal with heterophilic graphs, and to what extent they prevent over-squashing. Further, we outline open challenges and research
direction to stimulate future work

Published in Transactions on Machine Learning Research (02/2024)
Attending to Graph Transformers
Luis Müller
Deportment of Computer Science RWTH Aachen University
Mikhail Galkin
mikhail. @intel. com
Intel AI Lab
Ladislav Rampášek Isomorphic Labs
nempusel@tisooorriiilaa..cmm
Christopher Morris
morrs@ess.uth..aallee
Deportment of Computer Science RWTH Aachen University
Reviewed on OpenReview: /ttps://opentes
// optpr/veew.eeee...mm net/ forum? id- Hhb gH
Abstract
Recently, transformer architectures for graphs emerged as an alternative to established techniques for machine learning with graphs, such as suussage-passingg graph neural networks. So far, they have shown promising empirical results, e.g., on molecular prediction datasets, often attributed to their ability to circumvent graph neural networks' shortcomings, such as over-smoothing and over-squashing. Here, derive a laxonomy of graph transformer architectures, bringing some order to this emerging field. We overview their theoretical properties, survey structural and positional encodings, and discuss extensions for important graph classes, e.g., 3D molecular graphs. Empirically, we probe how well graph transformers can recover varions graph properties, how well they can deal with heterophilic graphs, and what extent they prevent. over-squashing Further, we outline open challenges and research direction to stimulate future work. Our code available at httts://githubb com luis wttssssmelleereeeee mwwueeerrprooingg. coaiiingggrraphe graph- graph-transeeeee transformers
1 Introduction
Graph-structured data are prevalent across application domains ranging from chemo- and bioinformatics (Barabasi & Oltvai 2004 Reiser et al. 2022 to image (Simonovsky & Komodakis 2017 and social-network analysis (Easley
& Kleinberg 2010). underlining the importance of machine learning methods for graph data. In recent years,
(message-passingg graph neural networks (GNNs) (Chami et al. 2022 Gilmer et al. 2017 Morris et al. 2021 were the dominant paradigm in machine learning for graphs. However, with the rise of transformer architectures (Vaswani
ct al. 2017) in natural language processing [Lin et al.) 2021b) and computer vision (Han et al., 2022), recently, a large number of works in the field focused on designing transformer architectures capable of dealing with graphs, so-called graph transformers (GTs).
Graph transformers have already shown promising performance Ying et al. 2021 e.g., by topping the leaderboard of the OGB Large-Scale Challenge (Hu et al. 2021 Masters al. 2022 in the molecular property prediction track. The superiority of GTs over standard GNN architecture is often explained by GNNs' bias towards encoding local structure and being unable to capture global or long-range information, often altributed to phenomena such as over-smoothing (Li et al. 2018), under-reaching (Barceló et al. 2020), and over-squashing (Alon & Yahay 2021 Di Giovanni et al. 2023). Many papers (Rampášck al., 2022) speculate that GTs do not suffer from such effects as they aggregate information over all nodes in given graph and hence are not limited to local structure bias. However, to make GTs aware of graph structure, one has to equip them with so-called structural and positional

---

Published in Transactions on Machine Learning Research (02/2024)
Graph Transformer
Encodings
[Bxe
Input Features [Sxx
Tokens [Sxc
Propagation [Sxe
Nodi-lise Rartone
Graphleed
Non-gonndtri
Gommtri
Nodra
Nodis
Falgos
Singgaph
Fully
Hully modiite
Postional Suuusural
Spane
Hybrid
GT SAN
SAN Graphi
Grapbomme
SE Traneoouuer
Gomple
Graplir
Gragh 5.0
Grugh
Rega Goiphormes Theneoemm-M
GMT Courloeeer MI.P-Miser NAGpharoes
GPS
Local Global Reletiv
Lond Clobal
Shortst path
TROECT TT CPPS MIP-MMser
GPS
GPS Spoeformer
3D distaliess
Emn-grap's Sunggupp
SEIS) Tonsformer
BCT TakesTT
GT TokenCT
Thnndomers-M
GKAT Explooreer
Relotive
Random walks
GPSI
Equilomec
Figure 1: Categorization of graph transformers along four main categories with representative architectures: Encodings; see Section 2.2 input features; see Section 2.3 tokens; see Section 2.4 propagation; see Section 2.5 See
also Figure 3 detailing how the different branches translate into changes to the original transformer.
encodings. Here, structural encodings are, e-g., additional node features to make the GT aware of (sub-)graph structure. In contrast, positional encodings make a node aware of its position in the graph concerning the other nodes.
Present Work. Here, we derive taxonomy of state-of-the-art GT architectures, giving an organized overview of recent developments. In addition, we survey common positional and structural encodings and clarify how they are rolated to GTss thcoretical propertics, c.g., their expressive power to capture graph structure. Additionally, we investigale these properties empirically by probing how well GTs can recover various graph properties, deal with heterophilic graphs, and what extent GIss alleviate the over-squashing phenomenon. Further, we outline open challenges and rescarch directions to stimulate future work. Our categorization, thcoretical clarification, and experimental study present a useful handbook for the GT and the broader graph machine-learning community. We hope that its insights and principles will help spur novel research results and avenues.
Related Work. Since GTs emerged recently, only a few surveys exist. Notably, Min et al. (2022a) provide a high-level overview of some of the recent GT architectures. Different from the present work, they do not discuss GTss theoretical and practical shortcomings and miss out on recent architectural advancements. Chen et al (2022a)
gives overview of GTs for computer vision. Finally, [Rampášek et al. (2022) provide general recipe for classifying GT architectures, focusing on devising empirically well-performing architectures rather than giving a detailed, principled overview of the literature.
1.1 Background
A graph G is a pair (V(G), E(G) with a finite set of nodes V(G) and a set of edges E(G) C Hu, CV u u v}. For case of notation, we denote an edge {u, o} as (u, v) or (v, u). In the case of directed graphs, E(G) S {(u, v) E (G)² и + v). Throughout the paper, we set n n== (V(G) and m = [E))). A node-altributed gruph G a triple (V(G), E(G),)), where X E gaxd for d O, a node feature matriz and X, is the node feature of node V(G). Similarly, we can represent edge features by an edge feature matris E E mmxe, for e >> O, where Evw is the edge feature of edge (v, w) E(G). The neighborhood of E V(G) is N(v) {u V(G) (u. E(G)). We say that two graphs G and H are isomorphic if there exists
aage-preserving bijection yp: V(G) - V(H), i.., (u, v) is in E(G) if and only if (j((u), s(b)) is in E(H) for all u, v E V(G). We denote a multiset by H.
Equivariance and Invariance. Ideally, machine learning models for graphs respect their symmetries, such as being agnostic to the node permutations other (group) transformations, such rotation, leading to the definitions of equiveriance and invarioacc. In particular, we can expect better generalization for models respecting these symmetries (Petrache & Trivedi 2023). In general (Fuchs et al.] 2021), given a transformation T, function f is equivariant if Transforming the vector input x is equal to transforming the oulput of the function f, i.e., f(Tx) = (x)). A function g is invariant if transforming the vector input x does not change the output, i.e., ((Tx) g(x). In the 3D Euclidean space, 3D translations, rotations, and reflections form the E(3) group. Translation and rotation form the SE(3) group. Rotations form the SO(3) group, rotations and reflections form the (3) group
2

---

Published in Transactions on Machine Learning Research (02/2024)
Graph Transformers. A transformer is stack of alternating blocks of multi-head attention and fully-counected feed--orwane nelworks. Let G be graph with node feature matrix X E R In each layer, & >> 0, given node feature matrix ( E Rn a single attention head computes
QK
Attn(X!0) = softmax
V
(1)
dd
where the softmax is applied row-wise, du denotes the feature dimension of the matrices Q and K, with X = X. Here, the matrices Q, K, and V are the result of projecting x(O) linearly,
Q = X K = and V VO
using three matrices Wq. W K E Rdxdx, and Wy Raxd, with optional bias terms omitted for clarity. Now, multi-head attention MultiHead (X()) concatenates multiple (single) attention heads, followed by an output projection the feature space of ((), By combining the above with additional residual connections and normalization, the transformer layer updates features ( via
((++1) FFN (MultiHead(xx)) X
Graph Neural Networks. Intuitively, GNNs learn a vector representing each node in a graph by aggregating information from neighboring nodes. Formally, let G be a graph with node feature matrix X E Rexd A GNN architecture consists of a stack of neural network layers, i.e., a composition of pernutationn-qquivariann parameterized functions. Each layer aggregates local neighborhood information, i.e., the neighbors' features, around each node and then passes this aggregated information on to the next layer. Following Gilmer al. (2017) and Scarselli et al. (2009), in each layer, t 0, we compute node features
h(-1) = (PD (h.*) (G (Th!) | ((N()) e R..
where (*D and (t) may be differentiable parameterized functions, e.g., neural networks. For example, GNNs often compute vector for node by using sum aggregation (Morris al. 2019 i.c.
h h((+1) a ( w(
Σ h hl! (EN(())
where is non-lincarity applicd in a point-wise fashion, w and ! E Bddd are parameter matricos, and
h (0) = X,. As noticed by Mialon al. (2021) we can rewrite attention as defined in Eq. 1 as
kexp
Attn(X (EV(G) EwEV (G) keep (!!) x
X XWWy,
(3)
for E V(G), where
kexp x(1)
(t) (()) == exp W WK//W/////
and obtain an aggregation reminiscent of GNN. fact, we may view a GT as special GNN, operating on a complete graph, where the attention score weights the importance of each node during the aggregation. Conversely, Veličković et al. (2018) propose graph attention networks (GAT), GNN that replaces sum aggregation with self-attention. We note that their definition of self-attention differs from Equation [ in that GAT replaces the dot-product with concatenation and subsequent linear projection.
2 The Landscape of Graph Transformers
In the following, we outline our taxonomy of GTTs, see also Figure D bringing some order to the growing set of GT architectures. We start by discussing the theorctical properties GTs that heavily rely on structural and
For simplicity, learn attention between graph's uodes. However, Section
2.4 extend this to, egg. edges subgraphs.
3

---

Published in Transactions on Machine Learning Research (02/2024)
positional encodings, which we study subsequently. Further, we discuss different approaches to dealing with essential classes of input node features, e.g., 3D coordinates in the case of molecules. We then study how to tokenize a graph, ie., partition a graph into atomic entities between which the attention is computed, e.g,, nodes. Then, we review how GTs organize message propagation in the graph through global, sparse, or hybrid attention. Finally, we overview represenlative applications of GTs..
2.1 Theoretical Properties
Tt is crucial to understand that the general GT architecture of Eq. (2) is less expressive in distinguishing non-isomorphic graphs than standard GNNs. Hence, it is also weaker in approximating permutation-invant invariant and -qqiivariant functions over graphs (Chen et al.] 2019). GTs are weaker since, without sufficiently expressive structural and positional encodings, they cannot capture any graph structure besides the number of nodes and hence equal DeepSets-like architectures (Zaheer et al. 2020 in expressive power. Thus, for GTss to capture non-trivial graph structure information, they are crucially dependent on such encodings; see below. In fact, by leveraging the results in Chen et al. (2019), it is easy to show that GTss can become maximally expressive, i... universal function approximators, if they have access to maximally expressive structural bias, e.g., structural encodings. However, this is equivalent to solving the graph isomorphism problem (Chen et al. 2019). Morcover, we stress that GNN architectures ures equipped with the same encodings will also possess the same expressive power. Hence, regarding expressive power, GTTs do not have an advantage over GNNs.
2023) study the connection between GNNs and graph transformers, showing that under mild assumptions, GNNs with virtual node connected to all other nodes are sulficient to simulate graph transformer. Conversely, Kim et al.] (2022) propose hierarchy of (higher-order) transformers and respective positional encodings that is aligned with k-IGNs [Maron et al. 2019), i.e., for each k >>> 1, there exists a corresponding higher-order transformer that can simulate a K-IGN. The relationship between k-IGNs and k-LL (Maron et al., 2019) then implies the connection between transformers and the k-WT, hierarchy as well.
Cai ct al.
2.2 Structural and Positional Encodings
As outlined in the previous subsection, GTs are crucially dependent on structural and positional encodings to capture graph structure. Although there is no formal definition or distinction between the two, structural encodings make the GT aware of graph structure on local, relative, or global level. Such encodings can be attached to node-, edge- or graph-level features. Examples of local structural encodings include annotating node features with node degroes (Chen et al. 2022b), the diagonal of the m-step random-walk matrix (Dwivedi et al. 2022). the time-derivative of the heal-kernel diagonal (Kreuzer et al.] 2021). enumerate count. predefined substructures and the node's 's role within (Bouritsas et al. 2002). or Ricci curvature (Topping et al. 2022). Examples of edge-level relative structural encodings include relative shortest-path distances (Chen et al. 2022a) or Boolcan features indicating if two nodes are in the same substructure (Bodnar et al., 2021). Examples of graph-level global
structural encodings include eigenvalues of the adjacency or Laplacian (Kreuzer et al. 2021 or graph properties such as diameter, number of connected components, or treewidth.
On the other hand, positional encodings make, e.g., node aware of its relative position to the other nodes in graph. Hence, two such encodings should be close to each other if the corresponding nodes are close in the graph. Again, we can distinguish between local, global, or relative encodings. Examples of node-level local positional encodings include the shortest-path distance of a node to a hub or central node or the sum of each column of the non-diagonal elements of the m-step random walk matrix. Examples of edge-level relative positional encodings are pair-wise node distances (Beaini et al. 2021 Chen et al.] 2022a. Kreuzer et al. 2021; Mialon ct al. 2021 Li et al. 2020) and relative random walk encodings (Ma et al. (002)). Examples of node-level global positional encodings
include eigenvectors of the graph Laplacian [Kreuzer et al. 2021 Dwivedi & Bresson 2020) (or of the Magnetic Laplacian in case of directed graphs (Geisler et al. 2023) }, or unique identifiers for each connected component of the graph. Lim et al. 2022)) propose SiguNet and BasisNet, two positional encodings also based on the eigenvectors of the graph Laplacian, which generalize a number of previously introduced structural and positional encodings such as those based on random walks (Dwivedi & Bresson 2020 Mialon et al. 2021 or PageRank (Li et al. 2020).
When designing such encodings, one must ensure equivariance or invariance to the nodes' ordering. Such equivariance is trivially satisfied for simple encodings such as node degree but not for more powerful encodings
4

---

Published in Transactions on Machine Learning Research (02/2024)
based on eigenvectors of the adjacency or Laplacian matrix (Lim et al.
2022
It is an ongoing effort to design
equivariant Taplacian-based encodings (Lim et al. 2022 Wang et al. 2022
2.3 Input Features
Besides characterizing GTs based on their use of structural and positional encodings, we can also characterize them based on their ability to deal with different node and edge features. To this end, we devise two families of input features. First, we consider so-called non-geometric features where nodes and edges have feature vectors in R4, ie., graphs are described with a tuple E, Secondly, we consider so-called geometric features where nodes and edges features contain geometric information, e.g., 3D coordinates for nodes X3D E R Therefore, graphs are described with (V, E, X, E, X E)D). We categorize GT architectures non-geometric and those supporting both features in the following.
Non-geometric GT& [Chen et al..
2022b Choromanski et al.
2021
Dwivedi & Bresson 2020 He et al.
2022 Kim
ct al. 2022 Kreuzer et al. 2021 Jain et al. 2021 Ma ct al.
2023
Mialon et al. 2021 Rampášck et al. 2022 are
most common and follow the equations in Section 1.1 Graphs with non-geomelric ural do not have explicit
geometric inductive bias. Examples of such features include encoded node attributes in citation networks or Iearnable atom-type emboddings in molecular graphs. Non-gcometric features are supposed be equivariant to node permutations, and transformers provide such equivariance by default. Structural and positional features (Section 2.20 are often added to increase the expressive power of GTs.
3D molecular graphs provide geometric fcatures describing nodes and edges, c.g., 3D coordinates of atoms, angles of bonds, or torsion angles of planes. Building GTss supporting geometric features is more challenging as geometric features need to be invariant or equirariant to certain group transformations, such as rotation, depending on the task. Further, the architectures must be invariant for graph-level molecular property prediction tasks. In contrast, models must be equivariant in node-level tasks such as predicting structural conformers or force fields.
Joshi et al. (2023) showed that equivariant geometric models more expressive than invariant ones. Here, we first describe (3()), SE(3), and E(3) equivariant models and then turn the attention to invariant models. TorchMD-NET (Thökke & Fabritiis 2022) achieves SO(3) equivariance by incorporating interalomic distances into the attention operation via exponential normal radial basis functions (RBF). Transforaee (Fuchs et al. 2020) was one of the first attempts to incorporate SE(3) equivariance. By using irreducible representations, Clebsch-Gordan coelficients, and spherical harmonics, the authors encode SE(3) equivariance into the attention operation. Equiformer (Liao & Smidt 2023) further extends this mechanism to complete E(3) equivariance. Graphormer (Shi al. 2022), Transformer-M (Luo et al. 2022a) and GPS++ (Masters et al. 2022) use Gaussian kernels to encode 3D distances between all pairs of atoms. Tailored for graph-level prediction tasks, GPS++ remains SF(3)-invariant, while Graphormer and Transformer-M introduce an additional (E(())-qqivariant prediction head for node-level molecular dynamics tasks.
2.4 Graph to Sequence Tokenization
The nature of graph tokenization, i.e., mapping a graph into a sequence of tokens, directly affects the supported features and computational complexity. Here, we identify three approaches to graph tokenization: (1) nodes as tokens, (2) nodes and edges as tokens, and (3) patches or subgraphs as tokens.
Using nodes as input tokens is the most common approach followed by many GTs, e.g., DDiivedi Bresson 2020 Fuchs et al. 2020 Kreuzer et al.) 2021 Luo et al. 2022b Rampášek al. 2022 Thölke & Fabrittis 2022 Ying et al. 2021 Here, we often treat structural and positional features as additional node features. Given graph with n nodes and the attention procedure of Eq. ( the complexity of such GTss is in O(n²). We note that more scalable, sparse attention mochanisms are also possible; see Section 2.5 Edge fcatures, e.g., shortest-path distances (Ying el al. 2021), random walk relative distances (Ma el al.) 2023), or relative 3D distances (Luo el al., 2022b Thölke & Fabritiis 2022), may be added as an attention bias given the fully computed attention score matrix with n² entries. Alternatively, Mialon et al. (2021); Jain al. (2021): Chen al. (2022b) leverage a GNN to incorporate node and edge features before applying transformer on the resulting node features. However, the transformer's quadratic complexity remains the bottleneck.
5

---

Published in Transactions on Machine Learning Research (02/2024)
The second approach uses nodes and edges in the imput sequence as employed by EGT (Hussain et al. 2022 and TokenGT (Kim et al., 2022). Turning an input graph into a graph of its edges is often used in moleculas GNNs (Gasteiger et al. 2021) and NLP (Yao et al. 2020). In addition to soft modeling the edges, ie., the node-to-node interactions, the attention operation also possibly models higher-order node-edge and edge-edge interactions that theoretically result in an expressiveness boost (Kim el al.) 2022). The input sequence can naturally incorporate node features, their positional encodings, and edge features. A pitfall of this approach is its O(n + m)) computational complexity. Since the approach includes edge features in the input sequence, such GTss might benefit from sparse attention mechanisms that do not materialize the full attention matrix.
The third approach relies on patches or subgruphs as tokens. In visual transformers Dosovitskiy ct al. 2021 such patches correspond to k x k image slices. A generalization of patches to the graph domain often corresponds to graph coarsening or partitioning (Back et al.) 2021 Chen et al. 2023 Kuang et al.) 2022 He et al. 2022 There, tokens are small subgraphs extracted with various strategies. Initial representations
tokens are obtained by passing subgraphs through a GNN using a form of pooling to a single vector. He ct al. (2022) adds token position features to the resulting vectors to distinguish coarsened subgraphs better. Finally, these tokens are passed through transformer with ((k2) complexity for graph with k extracted subgraphs. A similar approach is taken by NAGphormer (Chen et al. 2023) where tokens denote aggregated I-hop neighborhoods of a node. Each node is represented with a sequence of up to L tokens including the node itself and each token for / E [1, hop neighborhood. Subgraph tokenization is more scalable since the model never sees the whole graph and might benefit. from sampling methods. On the other hand, it makes GTSs inherently local and might hinder their long-range capabilitics.
2.5 Message Propagation
Most GTs follow the global all-to-all attention of Vaswani et al. (2017) between all pairs of tokens. In the initial GT (Dwivedi & Bresson| 2020) and TokenGT (Kim et al. 2022 this mechanism is unchanged, relying on token representations augmented with graph structural or positional information. Other models alter the global attention mechanism to bias it explicilly, lypically based on the input graph's 's structural properties. Graphormer (Ying et al. 2021 incorporates shortest-path distances, representation of edges along a shortest path, and node degrees. TransformerMM (Luo et al., 2022a) follows Graphormer and adds kernelized 3D inter-atomic distances. GRPE (Park et al. 2 considers multiplicative interactions of keys and queries with node and edge features instead of Graphormer's additive bias and additionally augments output token values. SAN (Kreuzer et al., 2021) relies positional encodings and only adds preferential bias to interactions along input-graph edges over long-distance virtual edges. GraphiT (Mialon et al.) 2021) employs diffusion kernel bias, while SAT (Chen et al. 2022b) develops GNN-based structure-aware attention kernel. EGT (Hussain et al. (202)) includes a mechanism akin to cross-attention to edge tokens to bias inter-node attention and update edge representations. Finally, Zhang et al. (2023) propose Praphormer-GD, a generalization of Graphormer, alongside new expressivity metrics based on graph biconnectivity for which Graphormer-Gi attains the necessary expressivity.
As standard global attention incurs quadratic computational complexity, it limits the application of graph transformers to graphs of up to several thousands of nodes. To alleviate this scaling issue, Choromanski et al. (2022) proposed GKAT based on a kernelized attention mechanism of the Performer (Choromanski et al. 2021 scaling linearly with the number of tokens. Another approach to improve GTss scaling is to consider a reduced attention scope, e.g., based on locality or sparsified instead of dense all-to-all, following expander graph-based propagation (Deac et al. 2022) as Exphormer (Shirzad et al., 2023). Finally, Wu et al. (2022) propose to view attention as in Equation 3) and then apply the kernel trick to keep to derive NodcFormer with a computational complexity that scales linearly with the number of nodes.
Finally, hybrid approaches combine several propagation schemes. For example, GPS and GPS++ (Rampášek et al. 2022 Masters et al. 2022) fuse local GNN-like architectures with global all-to-all attention into one layer. While GPS employs standard attention and can utilize linear altention mechanisms such as Performer [Choromanski attention conditioning. GraphTrans (Jain et al., 2021) is also a hybrid but applics stack of GNN layers first, followed by a stack of global transformer layers. Speeformer (Bo) ct al. 2023) employs transformer encoder layers for encoding eigenvalue representations and mixes those with node features in the graph convolution-style decoder. GOAT (Kong et al.] 2023) lets the nodes attend to k cluster
lt al. 2022). GPS++ follows Transformer-he
6

---

Published in Transactions on Machine Learning Research (02/2024)
centroids instead of n nodes on the global attention level. The centroids are obtained through k-means and exponential moving average. On the local level, nodes attend to their k-hop neighborhood.
3 Applications of Graph Transformers
Although GTss only emerged recently, they have already been applied in various application areas, most notably in molecular property prediction. In the following, we give an overview of the applications of GTss Kan et al. (2022) propose the Brain Network Transformers predict propertics of brain networks, c.g., the presence of discases stemming from magnelic resonance imaging. To that, they leverage rows of the adjacency matrix of each node structural encodings, which showed superior performance over Laplacian-based encodings in previous studies. Morcover, they devisc a custom pooling layer leveraging the fact that nodes in the same functional modulc tend to have similar properties. Liao & Smidt (2023): Thölke & Fabritiis 20222) see also Section 2.3 devise an equivariant transformer architecture to predict quantum mechanical properties of molecules. To capture the molecular structure, they encode atom types and the atomic neighborhood into a vectorial representation, followed by a multi-head attention mechanism. To predict scalar atom-wiss prediction, they rely on gated equivariant blocks (Schütt et al. 2021h, which then aggregated into single molecular predictions. Hu et al. (2020) develop approach to apply graph transformers to web-scale hetcrogencous graphs. During the attention computation, the authors use different projection matrices for each node and edge relation in the helerogeneous graph. Yao et al.. (2020) use transformers to tackle the graph-to-see se-quence problem, i.e., the problem of translating a graph to word sequences. They first translate a graph to its Levi graph, replacing labeled edges with additional nodes to incorporate edge labels. They then split such a graph into multiple subgraphs according to the different edge nodes. Each subgraph uses a standard transformer architecture learn the vectorial representation for each node. To incorporate graph structure, they mask out non-neighbors of a node, concentrating on the local structure. Finally, they concatenate multiple node representations. Further applications use transformers for rumor detection in microblogs (Khoo et al. 2020). predicting properties of crystals (Yan el al., 2022 or click-through rales [Min et al. 2022b1, or leverage them for 3D human pose and mesh reconstruction from a single image (Lin et al. 2021a
4 Experimental Study
Here, we conduct an empirical study to complement our taxonomy in a separate direction. Concretely, we empirically evaluate two highly discussod aspects of graph transformers: (1) the effectiveness of incorporating graph structural bias into GTs, and (2) their ability reduce over smoothinott and over-squashing. This study aims to compare selected methods from our taxonomy and investigate graph transformers more generally in terms of their potential benefits over GNNs. Note that empirical evaluation of all presented works would be out of scope for the present work. Instead we focus on the approaches most prevalent in the literature. Concretely, we aim to answer the following questions.
Q1 How well do different strategies for incorporating structural awareness into GTs contribute to recovering fundamental structural properties of graphs?
Q2 Does the ability of transformers to reduce over-smoothing lead to improved performance heterophilic datasets?
Q3 Do graph transformers alleviate over-squashing better than GNN models?
4.1 Structural Awareness of GTs
For question Q1, we evaluate the two most prevalent strategies for incorporating graph structure bias into transformers.
Positional and Structural Encodings (Section 2.2 Random- walk structural encodings (RWSE) and Lapla-
cian positional encodings (LapPE), two popular positional structural encodings for transformers (Rampášck
ct al. 2022
Attention Bias (Section 2.5 Attention bias based on spatial information such as shortest-path distance between nodes, following the Graphormer architecture (Ying et al. 2021).
7

---

Published in Transactions on Machine Learning Research (02/2024)
Table Hyper-parameter sets for GTs and GNNs with or without PE/SE (SET 1), and for Graphormer models (SET 2).
Hyper-parameter
SET
SET 2
Embedding dim.
64
72
Self-attention heads
Weight decay
10-5
10-2
Learning rate
10-3
10-3
Gradient clip norm
1.0
5.0
cosine,
LR scheduler
constant
warm--u 96
Batch size
256
Table 2: Average test accuracy of GTTs with structural bias (= SD) over five random seeds on the structural awareness tasks. Difficulty level on top derived from GIN performance. We additionally report the performance of a transformer without any structural bias serving as a baseline.
Easy
Medium
Hard
Model
EDGES
TRIANGLES-SMALL TRIANGLES-LARCE
CSL
2- 2-way Accuracy 10-way Accuracy 1 10-way Accuracy f 10-way Accuracy
GIN
98.11 #1.75
71.53 20.04
33.54 20.30
10.00 #0.00
Transforner
55.84 20.32
12.08 20.31
10.01 20.04
10.00
Transformer (LapPE)
98.00 #1.03
78.29 20.25
10.64 22.04
100.00
20.00
Transformer (RWSE)
97.11 +1.7a
99.40 40.10
54.76 47.24
100.00
+0000
Graphormer
97.67 20.97
99.09 20.31
42.34 20.48
90.00 20.00
We propose benchmark of three tasks that require increasingly higher structural awareness of non-geometric graphs. We determine the level of structural awarcness necessary to solve task according to the bascline performance of GIN (Xu et al. 2019), & 1-WL expressive GNN reference architecture. In addition, we report the performance of a vanilla transformer without any structural bias to understand the relative impact of the positional or structural encodings (PE/SE) and attention biasing.
We first describe the tasks in our benchmark and their estimated difficulty, then outline task-specific aper-parameters of evaluated models and interpret the observed results; see Table 2 for quantitative results.
Detect Edges (Easy). Detecting whether edge connects two nodes can be considered the fundamental test. for structural awarencss. We investigate this task using custom dataset, EDGES, derived from the ZINc (Dwivedi et al. 2023) dataset. For each graph, treat the pairs of nodes connected by an edge as positive examples and select an equal number of unconnected nodes as negative examples, resulting in a binary edge detection task with balanced classes. Let P denote the set of pairs selected either positíve negative examples, and let h,(") denote the feature vector of node after the last layer T of a model. We make predictions as follows. We first compute the cosine similarity between hT?)) and h!T)) for each pair (v, w) of nodes in P, resulting in a scalar similarity score. Finally, we apply linear layer each similarity score, followed by sigmoid activation, resulting in binary class probabilities.
Count Triangles (Medium). Counting triangles only requires information within node's immediate neighborhood. However, more than 1-WL expressivity is required to solve it (Morris et al. 2019). Hence, standard GIN architecture is not powerful enough. For this task, we evaluate models on the TRIANGLES dataset proposed by Kuyazev el al. (2019), which poses triangle counting as a 10-way classification problem. Here, graphs have between and 10 triangles, each corresponding to one class. The dataset specifies fixed train/ train/validaa http//vaalaaiitteeeee split, which a
we adopt in our experiments. Graphs in the train and validation split are roughly the same size. The test mixture of two graph distributions, where 50% are graphs with a similar size those in the training and validation set. (T CHIANGLES-SMAL. and 50% graphs of larger size A (TRUANGURS-LAAGGE) We separately report model
8

---

Published in Transactions on Machine Learning Research (02/2024)
performance for TRIANGLES-SMALL and TRIANGLES-LARGE to study the ability of transformers with different structural biases to generalize to larger graphs. We analyzed the datasets' class balance and report that each test set contains 5000 graphs with 500 graphs per class. For more details about the dataset, see Kuyazev et al. (011)).
1-WL limited model cannot distinguish non-isomorphic CSL graphs (Murphy et al. 2019) as the task requires an understanding of distance (Morris et al. 2019). Here, we evaluate models on the CSL dataset @Dwivedi et al. 2023), which contains 150 graphs with skip-link lengths ranging from 2 to 16 and poses 10-way classification problem. We follow Dwivedi et al. (0023) in training with 5-fold coossvalidation.
Distinguish Circular Skip Links (CSL) (Hard).
selection, we hand-designed two general sets of hyper- parameters; see [ For EDGES and TRIANGLES, we fix a parameter budget of around 200k for the transformer models, resulting in six layers for each model with the respoctive embodding sizes spocified Table | Further, we train Graphormer on 1k epochs. Due to the small number of graphs in the CSL datasel, we fix a parameter budget of around 100k for the transformer models, resulting in three layers for each model with the exact embedding sizes as above. Further, we train Graphormer on 2k epochs. We repeat cach experiment on five random seeds and report the model accuracy's 's mean and standard deviation.
Hyper-parameterd To simplify
For our 1-WL-equivalent reference model, we chose the GIN layer (Xu et al. the transformer models, we use a feed-forward neural network composed of the same components, using the same hyper- paremeearsstsss as for transformers. For Graphormer, we use the feod-forward neural network specified by Ying et al. 2021). Further, we train GIN with the Ser 1 hypet-parameters. For EDGES and TRIANGLES, this results in around 150k parameters, while for CSL, the GIN model contains approximately 75k parameters.
2019 To improve comparability with
Answering QI. Table P that GTs supplemented with structural bias generally perform well on all three tasks with a few exceptions. First, the GT with Laplacian positional encodings performs sub-par on the TRIANGLEs task. However, it is still an improvement over the I-WL-equivalent GIN. We hypothesize this is due to an expressivity limit of Laplacian encodings regarding triangle counting. Secondly, we observe that all models generalize poorly to larger graphs the TRIANGLES dataset. Lastly, observe that on CST. Graphormer cannot surpass 90% accuracy. A deeper analysis revealed that the shortest-path distributions can only distinguish 9 out of the 10 classes correctly, meaning that Graphormer is theoretically limited to at most 90% accuracy on CSL.
The above failure cases highlight that current graph transformers still suffer from limited expressivity, and no clear expressivity hicrarchy exists for the used positional or structural encodings. Morcover, GTs may generalize poorly to larger graphs. At the same time, we demonstrate a general superiority of structurally biased GTs over standard I-WLLequivalent models such as GIN. Both the transformer with RWSE as well as Graphormer solve EDGES, TRIANGLES-SMALL, and CSL almost perfectly, two of which pose a challenge for GIN, especially on CSL where GIN performs no better than random.
4.2 Reduced Over-smoothing in GTs?
Graph transformers are often ascribed with ability to cireumvent GNNs' over-smoothing problem due to their global attention mechanism. Thus, we set out to benchmark several variants of GCN (Kipf & Welling 2017 hybrid GPS models, and Graphormer on six heterophilic transductive datasets: ACTOR (Tang et al. 2009 ;;
CORNELL, TEXAS, WISCONSIN (CMU )001}; CHAMELEON and SQUIRREL [Rozemberczki et al. 2021 J. In addition, we also consider the recently proposed heterophilic datasets in (Platonov et al. 2023). which are significantly larger (ranging from 10k to 45k nodes), where we benchmark GCN (Kipf & Welling 2017). GAT (Veličković et al, 2018), as well as GPS. While over-smoothing can occur both on homophilic and heterophilic graphs, only on heterophilic graphs is over-smoothing truly limiting. This is because successfully predicting nodes' class heterophilic graph potentially requires a model to take into account nodes further away than those in the intermediate one or two-hop neighborhood and hence requires locally aggregating GNNs to be sufficiently deep. However, since graph transformers allow interactions between all pairs of nodes fewer layers might suffice to successfully solve a heterophilic problem.
For the six small datasets, we broadly follow the SET 1 search for each model variant to select the embedding size (32, 64, or 96) and dropout rates while we fix the
(Table D.
However, we perform a grid
9

---

Published in Transactions on Machine Learning Research (02/2024)
Table 3: Benchmarking of multiple model variants on six heterophilic transductive datasets. Here report average test accuracy (+ SD) over ten random seeds. We follow the dataset protocol of Pei et al. 2020 ; for additional
model comparison; see Luan et al. (2022).
Model (PE/SE type)
ACTOR
CORNELL
TEXAS
WISCONSIN
CHAMRLEON
SQUIRREI
Geom-GCN Pei al.
2020
31.59 41.15
60.54
1a.07
64.51
+3.60
66.76 +2.7
60.00 +2.81
38.15 +0.99
GCN (no PE/SE)
33.92 20.05
53.78
#5.07
65.95 =5.07
66.67 #2.05
43.14
=1.33
30.70 #1.17
GCN (LapPE)
34.30 #1.12
56.22 #2.00
65.95 #5.07
66.47 #1.37
43.53 =1.45
30.80 #1.88
GCN (RWSE)
33.69 21.07
53.78
62.97
69.41
43.84
31.77 4.0.5
GCN (DEG)
33.99 +00.1
53.51
+2200
66.76
#2.72
67.20 +1.88
46.36
=2.00
34.50 +:0.87
CIPGGCN+Taassore ELapPE)
37.68 20.52
66.22 #:3.87
75.41
=1..4
74.71
#2.97
48.57
=11.02
35.58 a.0.a
GPSCON Transformer
(RWSE)
36.95 +0.05
65.14 45.77
73.51
+2..65
78.04
4:2.88
47.57
4-0.90
34.78 #1.91
GPSCON Transformer (DEG)
36.91 +0.56
64.05
73.51
75.49
52.59
42.24 41..9
Transformer (LapPE)
38.43 =:0 87
69.46
=1.18
77.84
#1.00
76.08
#1.92
49.69
#1.11
35.77
#:0.0
Transformer (RWSE)
38.13 4.0.60
70.81
2.202
77.57
2.1.44
80.20
4.2.2
19.45
11.34
35.35
1.0.75
Transformer (DEG)
37.39 #0000
71.89
=2.46
77.30
#1.82
79.80
=:00
56.18
#0.55
43.64
2:0.00
Graphormer (DEG only)
36.91 a...s
68.38
1.1.7
76.76
2:1.79
77.06
2.1.07
54.08
4.0.5
43.20
2.0.82
Graphormer (DEG, attn. bias)
36.69
+00.0
68.38
76.22
77.65
53.84
43.75
Table 4: Benchmarking of multiple model variants on the five transductive node classification datasets proposed in Platonov et al. 2023). Here we report average test accuracy (+: SD) for ROMAN-EMPIRE and AMAzON- RATINGS and ROC AUC [ SD) for MINESWEEPER, TOLOKERS and QUESTIONS. Results over 10 splits, following PPlatonov et al.
2023
We highlight the first, second and third best results.
Model (PE/SE type)
ROMAN-
AMAZON- AMAZON-RATINGS
MINESWREPER
TOLOKERS
QUESTIONS
GCN
Platonov et al.
2023
73.69
48.70
89.75
10:30
83.64
10:97
76.09
GAT
Platonov et al.
2023
80.87
10:30
19.09 10.63
92.01 10.08
83.70
10:17
77.43 11.20
GCN (LapPE)
83.37 10:50
41.35 10:36
94.26 10.49
84.95
10.78
77.79
11.04
GCN (RWSE)
84.84 20.65
46.40 #0.85
93.84 #9.48
85.11
=0.77
77.81
4:1.40
GCN (DEG)
84.21 20.47
50.01
94.14 #0.50
82,51
20.80
76.96
GAT (LapPE)
84.80 =0.46
44.90 +00.3
93.50 +o.04
84.99
:0..4
76.55 =0.84
GAT (RWSE)
86.62 10.68
48.58 20.41
92.53 20.65
85.02
200.07
77.83 11:9
GAT (DEG)
85.51 -0.56
51.65
93.04 +0.62
84.22
77.10 -1.25
GPSGCN Performer
(TapPE)
83.96
48.20
93.85
84.72
77.85
GPSGCN+Peerorrue
(RWSE)
84.72 =0.05
48.08 #0.85
92,88 #0.00
84.81
+00.0
76.45 =1.61
CPSGCN-Ferforuer
(DEG)
83.38
20.68
18.93 100.4
93.60 10:47
80.49
10.97
74.24 1..38
GPSGAT Porformer
(LapPE)
85.93
20.82
48.86 20.99
92.62 20.79
84.62
20.54
76.71
GPSGAT Performer
(RWSE)
87.04 10.58
49.92 10000
91.08 20.58
84.38
2:0 91
77.14 17.49
GPSGATT+reforneer
(DEG)
85.54
51.03 +0.00
91.52 +0.46
82.45
+0..0
76.51
GISSGCN+Trsmnfonnee
(LapPE) (RWSE)
0OM
00M
91.82 +..41
83.51
+00.9
OOM
CPPGCN-TTanoffre
00M
O0M
91.17 #0.31
83,53
+.
OOM
GPSGCN Transformer (DEG)
OOM
OOM
91.76 1o.61
80.82
Le.90
OOM
GPSGAT Transformer
(LapPE)
OOM
OOM
92.29 20.61
84.70
OOM
GASGAT+ Transformer
(RWSE)
OOM
OOM
90.82
t...5
84.01
t.0.00
OOM
GAS Transformer
(DEG)
OOM
OOM
91.58
20.56
81.89
20.85
OOM
number of layers two. We implement the GCN and GT models following GPS with hybrid GCN+ Transfooooeeer aggregation layers but with the latter former component disabled, respectively. We train all models in full-batch mode using the entire graph as input.
For the live large datasets, we closely follow the hyper-parameter tuning and training setup described in Plltoonov et al,, 2023). To this end, we set the embedding size to 512 and only tune the number of layers (1, 2, 3, 4, and 5). Bocause on these datasots, the number of nodes provides an additional challenge for the transformer, we benchmark GPS also with the Performer module (Choromanski et al. 2022) to study the benefits of linear attention on large-scale graphs.
10

---

Published in Transactions on Machine Learning Research (02/2024)
1,0
0.8
0.8
Train
GCN
GGNN GAT
0.2
Transfomer
Problem radiu (depth)
Figure 2: Average train accuracy over ten random seeds of GT on the MECCHBORSMATCC dataset, compared to models from Alon & Yahav (2021).
Apart from Graphormer, we benchmark all models on three different positional/structural encodings, namely LapPE, RWSE, and degree encodings as described in Ying et al. 2021
Answering Q2. On the small datasets (Table 3 all transformer- based models outperform 2-layer GCN, and often the specialized Geom-GCN Pee et al. 2020). which experimental setup we follow. With the exemption of node degree encodings (DEG), other PE/SE had minimal effect on GCN's performance. Adding global attention to the GCN, i.., following the GPS model, universally improves the performance. Most interestingly, disabling the local GCN in GPS, i... becoming the Transformer model, increases the performance even further. Such results indicate that GNN-like models are unfit for these hetorophilic datasets, while the global attention of a transformer empirically facilitates considerably more successful information propagation. Graphormer, which utilizes node degree encodings, performs comparably to the Transformer counterparts. Surprisingly, the attention bias of Graphormer had no impact its performance. The shortest-path distance bias appears uninformative in these datasets, unlike, e.g., in ZINC, where we observed degradation from 0.12 test MAE to 0.54 when disabling the attention bias.
We conclude that we empirically confirm the expected benefits of global attention, albeit GTss do not achieve overall SOTA performance (e.g., see Luan et al.] (2022)), which is a reminder that specialized architectures can achieve similar or higher performance without global attention still.
On the large datasets (Table 4 we observe strong benefits of added positional//strucure encodings but also that their effect is highly dataset dependent. At the same time, added Transformer or Performer module does not yield improvements in general. Specifically, the full Transformer goes out of memory on the three largest datascts while leading to poor performance on MINESWEEPER and competitive performance on TOLOKERS. encodings and Transformer modules are achieved on
Interestingly, the largest improvements of positional/strucee ROMAN- EMPIRE, the only dataset with a large graph diameter (6824).
Here, we conclude that positional/structin attention only provides small no improvements at all. One possible explanation is that when applied to graphs with 10K more nodes, the self-attention of graph transformers is subjected to much more noise, which makes lcarning mcaningful long-range interactions difficult.
information can lead large gains in performance, while global
4.3 Reduced Over-squashing in GTs?
To answer question Q3, evaluate GT on the METCHBORSMATCH problem proposed by Alon & Yahav 2021 This synthetic datasct requires long-range interaction between leaf nodes and the root node of tree graph of depth d. The problem demonstrates GNNs' limited ability to transmit information across a receptive field that grows exponentially with d. We run our experiments with minimal changes to the code of Alon & Yahav) (2021) and train our transformer on depths 2 to 6. Note that GNN models fail to perfectly fit the training set of trees with depth 4. Convergence on NEIGHBORSMATCH can sometimes take up to 100k epochs for large depths Since the structure of the graphs in MATHH is irrelevant to solving the problem, we did not need to augment.
11

---

Published in Transactions on Machine Learning Research (02/2024)
node features with positional//truucuraal encodings or attention bias. Hence, the results represent most graph transformers that use global aggregation similar to the standard transformer. Otherwise, we used the same architecture as in Section
shows that the GT performs exceedingly better than the GNN baselines and can perfectly fit the training set even for depth d = 6. However, we note that the NEiGHBORSMATCH problem is idealized and has only limited practical implications. The core issue of over-squashing, which is squashing an exponentially growing amount of information into a fixed-size vector representation, is not resolved by transformers. Nonetheless, our results demonstrate that the ability of transformers to model long-range interactions between nodes can circumvent the problem posed by Alon & Yahav (2021).
Answering Q3. Section 4.3
5 Open Challenges and Future Work
Since the area of GTs is a new, emerging field, there are still many open challenges, both from practical and theoretical points of view. Theoretically, although it often claimed that GTss offer better predictive performance over GNNs and are more capable of capturing long-range dependencies and preventing over-smoothing and over-squashing, principled explanation still needs to be formed. Moreover, there needs to be a clearer understanding of the properties of structural and positional encodings. For example, it has yet to be understood when certain encodings are helpful and how they compare. The first step could be preciscly characterizing different encodings to distinguish non-isomorphicc graphis similar to the Weisfeiler Leman hierarchy (Morris el. al. 2021 ). Further, understanding GTTs generalization performance on larger graphs has yet to be understood similarly to GNNs (Yehudai et al. 2021 Zhou et al. 2022).
On the practical side, one major downside of GTss is their quadratic running time in the mumber of tokens, preventing them from scaling to truly large graphs typical in real-workd node-level prediction tasks. Moreover, due to the attention mechanism's nature, how best to incorporate edge features into GT architectures still needs to be determined. Further, our experimental analysis reveals a disadvantage of local GNN-like models when used in conjunction with transformers as in Rampašek et al. (2022) on heterophilic datasets. Heterophily is thus an open challenge, also for GTs. Morcover, it is crucial to incorporate expert or domain knowledge, c.g., physical or chemical knowledge for molecular prediction, into the allention matrix in a principled manner.
Explaining and interpreting the performance of GT's remains an open research area where we draw parallels with NLP. We posit that studying GT in the graph ML community follows similar path of studying transformer language models in NLP unified under the name of Bertology [Rogers el al. 2021 Vulié et al. 2020). Numerous Bertology studies reported that more than dissecting attention matrices and attention scores in transformer layers is needed for understanding how language models work. The community converged on designing datasets and tasks tailored to language model features such as co-reference resolution or mathematical reasoning. Therefore, we hepothesize that understanding GTss performance through attention scores is limited, and the community should focus on designing diverse benchmarks probing particular GTIs' properties. Further, studying scaling laws and emergent behavior of GTs and GNNs is still in its infancy, with few examples in chemistry (Frey et al. 2022) and protein representation learning [Ln et al. 2022
6 Conclusion
We have provided a taxonomy of graph transformers (GTs). To this end, we overviewed GTss theoretical properties and their connection to structural and positional encodings. We then thoroughly surveyed how GTs can deal with different imput features, e.g., 3D information, and discussed the different ways of mapping graph to sequence of tokens serving as GTss' input. Moreover, we thoroughly discussed different ways GTss propagate information and recent real-world applications. Most importantly, we showed empirically that different encodings and architectural choices drastically impact GTs' predictive performance. We verified that GTss can deal with heterophilic graphs and prevent over-squashig to some extent. Finally, we proposed open challenges and outlined future work. We hope our survey presents a helpful handbook of graph transformers' methods, perspectives, and limitations and that its insights and principles will help spur and shape novel research results in this emerging field.
12

---

Published in Transactions on Machine Learning Research (02/2024)
Acknowledgements
CM and LM are partially funded by a DFG Emmy Noether grant (468502433) and RWTH JPI Fellowship under Germany's i Excellence Strategy.
References
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
Jinheon Back, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In ICLR, 2021.
Alsert-Laszlo Barabasi and Zoltan N Oltvai, Network biology: understanding the cell's functional organization. Nature Reviews Genetics, 5(2):101-113, 2004.
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In ICLR, 2020.
Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pietro Lió. Directional graph networks. In JCML, pp. 748 758, 2021.
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. In ICLR, 2023.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and Lehman go cellular: CW networks. NewrIPS, pp. 2625 2640, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeirion, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. TPAMT, 2022.
Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the connection between MPNN and graph transformer. In ICML, pp. 3408-3430, 2023.
Ines Chami, Sami Abu-al-Haija, Bryan Perozzi, Christopher Ré, and Kevni Murphy. Machine learning graphs:
A model and comprehensive taxonomy. JMLR, pp. 1 1-64, 2022.
Chaoqi Chen, Yushuang Wu, Qiyuan Dai, Hong- Yu Zhou, Mutian Xu, Sibei Yang, Xiaoguang Han, and Yizhou Yu. A survey graph neural networks and graph transformers in computer vision: A task-oriented perspective. ArXiv, 2022a.
Dexiong Chen, Leslic O'Bray, and Karston Borgwardt. Structure-aware transformer for graph representation learning. ICML, 2022b.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun Hc. NAGphormer: A tokenized graph transformer for node classification in large graphs. ICLR, 2023.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In NewrIPS, pp. 15868-1588 2019.
Krzysztof Choromanski, Han Lin, Haoxian Chen, Tianyi Zhang, Arijit Sehanobish, Valerii Likhosherstov, Jack Parker-Holder, Tamas Sarlos, Adrian Weller, and Thomas Weingarten. From block-Toeplitz matrices to differential equations on graphs: towards general theory for scalable masked transformers. In ICML, 2022.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreca Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with performers. In ICLR, 2021.
CMU. World Wide Knowledge Base (Web-KB) project. http://www.ccm cs cmu. adu/afs/cee afs/cs../s/sss//ass cmu, edu/project/ theo-11/ww//wkbe 2001.
13

---

Published in Transactions on Machine Learning Research (02/2024)
Andreea Deac, Marc Lackenby, and Petar Veličković. Expander graph propagation. In Learning Graphs Conference, 2022.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M. Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In ICML, pp. 7865 7885, 2023.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostala Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreil, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. ArXiv, 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua. Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In ICLR, 2022.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. JMLR, 2023.
David Easley and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Counected World. Cambridge University Press, 2010.
Nathan Frey, Ryan Soklaski, Simon Axelrod, Siddharth Samsi, Rafael Gomez-Bombarrlli Connor Coley, and Vijay Gadepally. Neural scaling of deep chemical models. chemRriv, 2022.
Fabian Fuchs, Daniel F. Worrall, Volker Fischer, and Max Welling. ST(3)-Transformers: 3D roto-translation equivariant attention networks. In NeurIPS, 2020.
Fabian B. Fuchs, Edward Wagstaff, Justas Dauparas, and Ingmar Posner. Iterative SE(3)-Transformers In Geometric Science of Information, pp. 585 595, 2021.
Johannes Gasteiger, Florian Becker, and Stephan Günnemann. Gemnet: Universal directional graph neural networks for molecules. NewrIPS, pp. 6790 6802, 2021.
Simon Geisler, Yujia Li, Daniel Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cosmin Paduraru. Transformers meet directed graphs. Tn JCML, 2023.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry, In JCML, pp. 1263 1272 2017.
Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al. survey on vision transformer. TPAMI, 2022.
Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of ViT/MLP-mixen to graphs. Arxiv, 2022.
Dan Hendrycks and Kevin Gimpel. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. ArXio preprint, 2016.
Matthew Honnibal, Ines Montani, Sofie Van Landeghem, and Adriane Boyd. spaCy: Industriallstrenggh Natural Language Processing in Python. 2020.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskover. OGB-LSC: A large-scale challenge for machine learning on graphs. In NeurIPS: Datasets and Benchmarks Track, 2021.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogencous graph transformer. In WWW, pp. 2704 2710, 2020.
Md Shamim Hussain, Mohammed J Zaki, and Dharmashankar Subramanian. Global self-attention as a replacement for graph convolution. In KDD, pp. 655 665,6 2022.
14

---

Published in Transactions on Machine Learning Research (02/2024)
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. NewrIPS, 2021.
Chaitanya K. Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Lio. On the expressive power of geometric graph neural networks. In ICML, pp. 15330-15355, 2023.
Xuan Kan, Wei Dai, Hejie Cui, Zilong Zhang, Ying Guo, and Carl Yang. Brain network transformer. ArXiv, 2022.
Ling Min Serena Khoo, Hai Leong Chieu, Zhong Qian, and Jing Jiang. Interpretable rumor detection in microblogs by attending to user interactions. In AAAI, pp. 8783 8790, 2020.
Jinwoo Kim, Tien Dat Nguyen, Sconwoo Min, Sungjun Cho, Moontac Lec, Honglak Lee, and Scunghoon Hong. Pure transformers are powerful graph learners. In NewrIPS, 2022.
Thomas N. Kipl and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. In NewrIPS, pp. 4202 4212, 2019.
Kezhi Kong, Jiuhai Chen, John Kirchenbaner, Renkun Ni, C. Bayan Bruss, and Tom Goldstein. GOAT: A global transformer on large-scale graphs. In ICML, 2023.
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In NeurIPS, 2021.
Weirui Kuang, Zhen Wang, Yaliang Li, Zhewei Wei, and Bolin Ding. Coarformer: Transformer for large graph via graph coarsening. OpenReriew, 2022.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In NewrlPS, 2020.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, pp. 3538-233 1348-355,,41 2018
Yi-Luu Liao and Tess Smidt. Equiformer: Equivariant graph attention transformer for 3D atomistic graphs. In ICLR, 2023.
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, 2022.
Kevin Lin, Lijuan Wang, and Zicheng Liu. Mesh graphormer. In ICCV, pp. 12919-12928, 2021a.
Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. A survey of transformers. ArXiv, 2021b.
Zeming Lin, Halil Akin, Roshan Rao, Brian Hie, Zhongkai Zhu, Wenting Lu, Nikita Smetanin, Allan dos Santos Costa, Maryam Zazal-Zarandi, Tom Screu, Sal Candido, al. Language models of protein sequences the scale of evolution enable accurate structure prediction. bioRriv, 2022.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In NewrIPS, 2022.
Shengjie Luo, Tianlang Chen, Yixian Xu, Shuxin Zheng, Tie- Yan Liu, Liwei Wang, and Di He. One transformer understand both 2D & 3D molccular data. ArXiu, 2022a.
Shengjie Luo, Shanda Li, Shuxin Zheng, Tie Yan Liu, Liwei Wang, and Di He. Your transformer may not be as powerful as you expect. ArXio, 2022b.
Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puncet K. Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. Tn TCML, 2023.
15

---

Published in Transactions on Machine Learning Research (02/2024)
Haggai Maron, Heli Ben-Hamm: Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NewrIPS, pp. 2153 153-2164, 2019.
Dominic Masters, Josef Dean, Kerstin Klaser, Zhiyi Li, Sam MadddrellManner, Adam Sanders, Hatem Helal, Deniz Beker, Ladislav Rampášek, and Dominique Beaini. GPS++: an optimised hybrid MPPN/transformn for molecular property prodiction. ArXiv, 2022.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT: Encoding graph structure in transformers. ArXiv, 2021.
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Poilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. ArXiv, 2022a.
Erxue Min, Yu Rong, Tingyang Xu, Yatao Bian, Da Luo, Kangyi Lin, Junzhou Huang, Sophia Ananiadou, and Peilin Zhao. Neighbour interaction based click-through rate prediction via graph-masked transformer. In SIGIR, 2022b.
pp.
C. Morris, Y. L., H. Maron, B. Rieck, N. M. Kriege, M. Grohe, M. Fey, and Borgwardt. Weisfeiler and Leman go machine learning: The story so far. ArXiv, 2021.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Ganrav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, pp. 4602 4609, 2019.
Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak A. Rao, and Bruno Ribeiro. Relational pooling for graph representations. In ICML, pp. 4663 4673, 2019.
Wonpyo Park, Woonggi Chang, Donggeon Lee, Juntac Kim, and Scung won Hwang. GRPE: Relative positional encoding for graph transformer. ArXio, 2022.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gon: Geometric graph convolutional networks. In ICLR, 2020.
Mircea Petrache and Shubhendu Trivedi. Approxinatioo-ggeemllaaaaoo trade-offs under (approximate) group equivariance. In NeurIPS, 2023.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Lindmila Prokhorenkova. A critical look the evaluation of gnns under heterophily: Are really making progress? In ICLR, 2023.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. In NewrIPS, 2022.
Patrick Reiser, Marlen Neubert, André Eberhard, Luca Torresi, Chen Zhou, Chen Shao, Houssam Metni, Clint van Hoesel, Henrik Schopmans, Timo Sommer, et al. Graph neural networks for materials science and chemistry. Communications Materials, 3(1):93, 2022.
Anna Rogers, Olga Kovaleva, and Anna Rumshisky. A primer in bertology: What we know about how bert works. TACL, 8:842 866, 2021.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 922:cna,, 2021.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
Kristof Schütt, Oliver T. Unke, and Michael Gastegger. Equivariant message passing for the prediction of tensorial properties and molecular spectra. In ICML, pp. 917799377779 2021.
Yu Shi, Shuxin Zheng, Guolin Ke, Yifei Shen, Jiacheng You, Jiyan He, Shengjie Luo, Chang Liu, Di Hc, and Tic-Yan Liu. Benchmarking graphormer large-scale molecular modeling datasets. ArXiv, 2022.
16

---

Published in Transactions on Machine Learning Research (02/2024)
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Scaling graph transformers with expander graphs. In ICMT, 2023.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neural networks on graphs. In CVPR, pp. 19-38, 2017.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In KDD, 2009.
Philipp Thölke and Gianni De Fabritiis. Equivariant transformers for neural network based molecular potentials. In ICLR, 2022.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In JCLR, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NewrIPS, pp. 5998 6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio, Graph attention networks. In ICLR, 2018.
Ivan Vulić, Edoardo Maria Ponti, Robert Litschko, Goran Glavaš, and Anna Korhonen. Probing pretrained language models for lexical semantics. In EMNLP, pp. 7222-7240 2020.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In ICLR, 2022.
Qitian Wu, Wentao Zhao, Zenan Li, David P. Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. In NeurlPS, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In TCLR, 2019.
Keqiang Yan, Yi Liu, Yuchao Lin, and Shuiwang Ji. Periodic graph transformers for crystal material property prodiction. In NeurIPS, 2022.
Shaowei Yao, Tianming Wang, and Xiaojun Wan. Heterogeneous graph transformer for graph-to-sequence learning. ACL, pp. 7145-7154, Online, 2020.
Gilad Ychudai, Ethan Fotaya, Eli A. Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In ICML, pp. 11975 11986, 2021.
Chengruan Ying, Tianle Cai, Shengjic Luo, Shuxin Zheng, Guolin Ke, Di Hc, Yanming Shen, and Tic- Yon Liu. Do transformers really perform badly for graph representation? In NewrIPS, 2021.
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. NewrIPS, 2020.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In ICLR, 2023.
Yangze Zhou, Gitta Kutyniok, and Bruno Ribciro. OOD link prediction generalization capabilitics of messago-passing GNNs in larger test graphs. In NewrIPS, 2022.
17

---

Published in Transactions on Machine Learning Research (02/2024)
X 1+1
E El+1
Gl+1
sum & nom
FFN
sum & norm
Standard attention
Modified attention
Attention Propagation
Sparse attention
Hybrid attention
X
E
G
Tokens
Nodes
Edges
Subgraphs
Input Features
Non-geometric
Geometric
Encodings
Positional
Structural
Edge-level
Graph-level
Figure 3: Overview of how the different branches of our taxonomy affect the original transformer architecture.
A Dataset Details
Here, describe the datasets used in experiments; Table for overview the datasct statistics.
Edges We derive the EDGES dataset from ZING Dwivedi et al. 2023 ZiNc compriscs 12K molecules from the ZINC database with heavy atoms as nodes and bonds as edges. The original task of ZINC is to predict the constrained solubility of a given molecule. Note that we ignore these regression targets in our link prediction task.
The TRIANGLES dataset contains syuthetic graphs with the goal of predicting the number of triangle subgraphs contained in a given graph (Knyazev et al. 2019).
Triangles
CSL The CSL datasct contains synthetic regular graphs, i.., graphs where each node has the same number of neighbors (Dwivedi et al. 2023). The nodes of each graph initially form eycle and are then additionally equipped
18

---

Published in Transactions on Machine Learning Research (02/2024)
with additional edges, so-called skip links, connecting nodes on the cycle that some fixed length L apart. Different graphs are constructed for different skip link lengths L. and the task of CSL is to classify L.
Actor The ACTOR dataset is derived from the film-diredooractto--viiee network, heterogeneous graph resulting from crawled Wikipedia pages and proposed in Tang al. (2009). Specifically, ACTOR is graph where actors are the nodes, and two actors are connected by edge if their names occur on the same Wikipedia page. The task is to classify the actors in one of the five most occurring categories in the category information on the respective actor's Wikipedia page.
Cornell, Texas, Wisconsin The CORNELL, TEXAS and WISCONSIN are three of the four webpage networks collected in WebKB (CMU) 2001). Each network contains crawled webpages as nodes and hyperlinks connecting the pages as edges. The lask is to predict which category of student, project, course, staff, and faculty a webpage belongs to.
Chameleon, Squirrel The CHAMELEON and SQUIRREI, are datasets constructed from Wikipedia pages of their respective topic (that of Chameleons and that of Squirrels, respectively), where the nodes are articles and edges represent links from one article to another (Rozemberzzki et al.) 2021). p. The node features are based on the occurrence of particular nouns on the respective article and the task is to predict the average monthly traffic on the site.
The ROMAN-EMPIHH dataset is based on the Wikipedia article of the Roman Empire (Platonov ct al. 2023 where nodes are the words occurring in the article and an edge between two words indicates that either the words follow each other sentence or if one word syntactically depends on the other. The task to predict the syntactic role of the work according to spaCy (Honnibal et al. 2020).
Jooann-Empire
Amazon-Rating The AMAZON-RATING dataset is derived from Amazon product co-purchasing metadata PPatoonov et al. 2023), where the nodes are products and an edge between two products indicates that the products are frequently bought together. The task is to predict the average rating of the product from one to five stars.
Minesweeper The MINESWEEPER dataset is constructed from a grid graph, where each node represents a cell in a Minesweeper game, and the task is to predict for each cell whether contains a mine (Platonov et al. 2023
Tolokers The TOLOKERS dataset contains data from the Toloka crowd-sourcing platform Platonov et al. 2023 Nodes represent workers, and an edge between two workers indicates that the workers have worked together on one of 13 selected projects. The task is to predict which workers have been banned from a project.
The QUESTIONS dalaset contains data from a questlion-answering wbesite (Platonov et al. 2023) Nodes represent users answering questions on medicine, and an edge between two users indicates that the users have answered the same questions within some fixed time span. The task is to predict which users remained active at the end of the time span.
Questions
B Experimental details
Here, we describe the details of our experiments. All experiments were run on single A100 NVIDIA GPU with 80GB of GPU RAM.
We base our implementation on GraphGPS (Rampášek et al. 2022 which is available at https://githubb com/ Sampaasek/CraphGPP which also includes an implementation of Graphormer (Ying et al. 2021), except for the over-squashing experiment, where we use the implementation by Alon & Yahav (2021) to stay as close as possible to the original implementation. All model layers first apply a wwwoolutionaatteniiion followed by a feed-forward network. The resulting embeddings are then fod into final MLP head to make a prediction. For all models, we use a GELU non-linearity (Hendrycks & Gimpel 2016) in the connections for all models, one after the convolution aatinntionnnntiiinnnioie and one after the ford-forward network.
network. Further, we apply residual
19

---

Published in Transactions on Machine Learning Research (02/2024)
Table 5: Statisties of the datasets used our experiments (Dwivedi et al.
2023 Knyazev et
2019
Tang et al.
2009
CMU 2001
Rozemberezki et al. 2021 Platonov et al., 2023
Dataset
Num. graphs
Num. nodes
Num. edges
Task
Metric
EDGES
12,000
277,864
597,970
Link prediction
Cross entropy
TRIANGLES
45,000
938,438
2,947,024
10-way graph classification
Cross entropy
CSL
150
6,150
24,600
10-way graph classification
Cross entropy
ACTOR
7,600
30,019
5-way node classification
Cross entropy
CORNELL
298
5-way node classification
Cross entropy
TEXAS
1
183
325
5-way node classification
Cross entropy
WISCONSIN
1
251
615
5-way node classification
Cross entropy
CHAMELEON
1
2,277
36,101
5-way node classification 5-way node classification
Cross entropy
SQUIRREL.
5,201
217,073
Cross entropy
ROMAN-EMPIRE AMAZON-RATING
1
22,662
32,927
18 18-way node classification
Cross entropy
24,492
93,050
5-way node classificution
Cross entropy
MINESWEEPER
10,000
39,402
2-way node classificution
Cross entropy
TOLOKERS
11,758
519,000
2-way node classifiention
Cross entropy
QUESTIONS
48,921
153,540
2-way node classification
Cross entropy
For the structural awareness experiments in Section 4.1 we follow the hyper-parameters detailed in Table 1 In addition, for all models, we use six layers of convolution/atten atttention. For the GIN, Transformer, and GPS, we use batch normalization, mean pooling, and three layers for the final MLP head. For Graphormer, we use layer normalization, [graph] token readout, and a linear layer, preceded by a final layer norm for the final MLP head, following (Ying al. 2021).
For the six small datasets ACTOR, CORNELL, TEXAS, WISCONSIN, CHAMBLEON and SQUIRREL, select hyper-pant prper-parameters with grid search over the hidden dimension (32, 64, 96), dropout (0.0, 0.2, 0.5, 0.8) and, where applicable, attention dropout (0.0, 0.2, 0.5). For the grid scarch, we repeat cach experiment ten times and select the hyper-paramelers leading to the best average validation performance. In all models, we use two layers of convolution/ attention and a linear layer for the final MLP head. We use batch normalization for the GCN, GPS, and Transformer and layer normalization for Graphormer. Again, for Graphormer, we apply a final layer norm before the final MLP head.
For the five large datasets in Platonov et al. 2023 fair comparison. As result, only tune the number of layers (1,2,3,455). We use pooling and linear layer for the final MLP head.
follow their hyper-parameter selection exactly to enable
20


Reviews:
[{"review_id": "UAOtm5eLnG", "reviewer": "Reviewer_Limv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1. The paper has comprehensive evaluation of graph transformers.\n2. It offers a detailed taxonomy, providing clarity on different types of graph transformer architectures. \n\n# Weaknesses\n1. The taxonomy raises several questions for study - how do various encoding strategies fare for various downstream tasks?, which transformers scale better with graph size?, etc. However, one of these questions have been answered in the experiment section.\n2. The experiment section largely deals with comparing GNN and GTs on oversmoothing and oversquashing problems with some discussion on comparison with GTs. While this is valuable result to know, but it is unclear as to how the insights provided connect with the taxonomy proposed in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a comprehensive study of graph transformer architectures in machine learning. It introduces a taxonomy of graph transformers which categorizes graph transformers based on several key aspects. It includes the types of transformers, focusing on their architecture and how they process graph data. The taxonomy considers aspects like how these transformers encode structural and positional information of graphs, and how they handle different input features. This classification helps in understanding the diverse approaches and methods used in graph transformer models, providing a structured way to compare and analyze their capabilities and applications in various machine learning tasks. The paper also explores their applications, particularly in 3D molecular graphs, and investigates their effectiveness in recovering graph properties, dealing with heterophilic graphs, and preventing over-squashing. The paper aims to provide insights and directions for future research in this field.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the paper will be a very valuable contribution. However, the experiment section as it stands today is very lacking. A paper proposing to give taxonomy for graph transformer should provide a detailed study across the various axes in the taxonomy (at least to a degree that seems doable). Only one question (Q1) largely compared along a proposed axis in the taxonomy. However, the other two question (Q2 and Q3) largely dealt with GNNs vs GT questions. I would suggest incorporating more questions that compares GTs along more axes which will likely provide a detailed understanding of GTs while proving the value of the proposed taxonomy for research purposes.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oqJX26xe8D", "reviewer": "Reviewer_Jn7n", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nThe survey is in general quite inclusive and timely.\n\nThe experiments are useful as they indeed provide sensible answers.\n\n\nWeaknesses:\nThe criteria of the taxonomy are disconnected from the experiments. The paper is a set of useful sections but is not connected sufficiently. It could be interesting to expand upon how the experimental answers correlate with the taxonomy e.g. how does over-smoothing correlate with the type of input features and message passing? It is important for a survey to be consistent.\n\nThe theoretical considerations, which are a vital part of separating the current survey from others, are quite limited. The authors address briefly the models’ expressive power and some comparison with GNNs, but do not include differentiation of the methods in Figure 1 based on their theoretical properties neither they expand enough to understand the intuition behind some arguments of the paper e.g. why SE(3) group defines a clear distinction in 2.3. \n\nThe applications could be more elaborate, the list misses for example this prominent paper:\nHu, Z., Dong, Y., Wang, K., & Sun, Y. (2020, April). Heterogeneous graph transformer. In Proceedings of the Web Conference 2020 (pp. 2704-271", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The current paper is a technical survey of graph transformer methodologies and includes a theoretical analysis of the models, empirical differences between them, and the potential of future extensions.\n\nThe survey starts with a small background overview of graph theory, graph transformers, and graph neural networks. Subsequently, the literature is broken down and analyzed in detail based on five different criteria. The first is the models’ provable expressive power and overall theoretical properties. The second is the encoding type of the input features, while the third is the input features category.\nThe fourth section refers to approaches that utilize the graph as a sequence similar to NLP. The final section separates papers based on their way of using attention to combine neighboring nodes’ features. \nThe subsequent sections include a short overview of applications and an experimental study that aims to examine the ability of graph transformers to recover structural properties, perform on heterophilic datasets, and reduce over-squashing. The extensive experiments indicate a ranking between a number of graph transformer methods in all three tasks. The answers are informative and concise.\n\nFinally, the paper concludes with a summary of current limitations and potential future work.\nOverall, the paper is interpretable and inclusive enough to be considered a useful handbook for graph transformers.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Apart from addressing the aforementioned weaknesses, some structural properties of the paper such as:\nFigure 1 should be closer to section 2 (possibly page 4). The hierarchical structure could include more information to make the scheme more independent or the information could be added in the caption.\n\nAll tables in the experimental section should be closer to the text describing them.\n\nI believe it is more sensible to first introduce GNNs and then move to graph transformers, and the same applies to sections 2.2 and 2.3.", "broader_impact_concerns": "There is no evident concern as the paper is a survey.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QCaEaAWICz", "reviewer": "Reviewer_7Lg5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Comprehensive Coverage: The survey provides an extensive and timely overview of various Graph Transformer methods. Its broad scope ensures a thorough understanding of the field's current state and recent developments.\n2. Clarity and Accessibility: The paper is particularly commendable for its clear and accessible presentation, especially regarding the motivation and taxonomy of Graph Transformers. This approach makes it easier for newcomers to quickly grasp the essential concepts of the graph transformer field.\n3. Empirical Contribution: Empirical Contribution: Beyond merely summarizing existing methods, the survey incorporates empirical studies to validate previous concepts. This addition is a valuable contribution to the community.\n\nWeakness:\nThe primary limitation of this survey is its limited depth, particularly for those new to the field. While it effectively categorizes GT methods from various angles, such as Structural and Positional Encodings, Message Propagation, and Graph to Sequence Tokenization, the paper relies heavily on text descriptions when detailing model differences. To enhance understanding, it would be beneficial to incorporate illustrative figures that highlight key trends and distinctions. Additionally, for the datasets featured in the survey, a tabular summary outlining the specific tasks they are designed for and their estimated difficulty levels would be valuable. This approach would provide readers with a clearer and more comprehensive overview of the datasets and their relevance in the context of graph transformers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper serves as a comprehensive survey, focusing on recent developments in Graph Transformer (GT) architectures. It specifically provides a taxonomy of Graph Transformers, offering an organized framework for understanding these models. The authors delve into the theoretical properties of Graph Transformers and their relationship with structural and positional encodings. This survey also covers the diverse ways in which Graph Transformers process various input features. \n\nFurthermore, they discuss the different methods through which Graph Transformers disseminate information, alongside their recent applications in real-world scenarios. Additionally, their investigation extends to empirical analysis, examining Graph Transformers' ability to discern various graph properties, handle heterophilic graphs, and mitigate the over-squashing phenomenon. Lastly, the paper summarizes the current challenges in the field of Graph Transformers and proposes directions for future research, paving the way for further advancements in this domain.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to suggest that the authors enhance the paper by including illustrative figures for some of the more influential methods, in order to deepen the technical understanding. Additionally, incorporating a table that summarizes the datasets, along with the specific tasks they are intended for and their estimated difficulty levels, would greatly improve the paper's clarity and usefulness.", "broader_impact_concerns": "I do not have any concerns about the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The chief concern among reviewers was that the two main contributions of this work (the taxonomy and the empirical results) appear disconnected. For example, the empirical study raises questions about "over-smoothing" and "over-squashing" (Q2, Q3) but these are not discussed at all in Section 2, which concerns the taxonomy. Conversely, many of the differences between methods included in the taxonomy are not evaluated in the empirical study. 

These discrepancies do not make the paper incorrect, or take away from potential interest, but I fear that many readers will have the same reaction to the paper, even after the first revision made by the authors. For the camera-ready version, I recommend that the presentation be improved further to align or compare the two goals of the paper. For example, does the taxonomy help in answering the empirical questions or is it entirely separate? Why is the selected subset of methods used in the empirical study appropriate, in light of the larger taxonomy?
Decision: Accept (poster)