Exphormer: Scaling Graph Transformers with Expander Graphs
Authors: Hamed Shirzad
Ameya Velingker
Balaji Venkatachalam
Danica J. Sutherland
Ali Kemal Sinop
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph neural networks
Transformers

Abstract: Graph transformers have emerged as a promising architecture for a variety of graph learning and representation tasks. Despite their successes, it remains challenging to scale graph transformers to large graphs while maintaining accuracy competitive with message-passing networks. In this paper, we introduce Exphormer,  a framework for building powerful and scalable graph transformers.  Exphormer consists of a sparse attention mechanism based on expander graphs, whose mathematical characteristics, such as spectral expansion, and sparsity, yield graph transformers with complexity only linear in the size of the graph, while allowing us to prove desirable theoretical properties of the resulting transformer models. We show that incorporating Exphormer into the recently-proposed GraphGPS framework produces models with competitive empirical results on a wide variety of graph datasets, including state-of-the-art results on three datasets. We also show that Exphormer can scale to datasets on larger graphs than shown in previous graph transformer architectures.

Under review as a conference paper at ICLR 2023
EXPHORMER: SCALING GRAPH TRANSFORMERS WITH EXPANDER GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph transformers have emerged promising architecture for a variety of graph learning and representation tasks. Despite their successes, though, it re- mains challenging to scale graph transformers large graphs while maintaining accuracy competitive with message- message-passing networks. In this paper, we introduce Exphormer, a framework for building powerful and scalable graph transformers. EXPHORMER consists of sparse attention mechanism based on expander graphs, whose mathematical characteristics, such as spectral expansion, pseduorandom- ness, and sparsity, yield graph transformers with complexity only linear in the size of the graph, while allowing us to prove desirable theoretical properties of the resulting transformer models. We show that incorporating EXPHORMER into the GraphGPS framework produces models with competitive em- pirical results wide variety of graph datasets, including state of of-tthear art results on three datasets. We also show that EXPHORMER can scale to datasets on larger graphs than shown in previous graph transformer architectures.
INTRODUCTION
Graph learning has become an important and popular area of study that has yielded impressive results on a wide variety of graphs and tasks, including molecular graphs, social network graphs, knowledge graphs, and more. While much research around graph learning has focused on graph neural networks (GNNs), which are based on local message-passingg graph learning that has garnered much interest involves the use of graph transformers (GT's.. Graph transformers largely operate by encoding graph structure the form of a soft inductive bias. These can be viewed as graph adaptation of the Transformer architecture (Vaswani al. (017) that are successful in modeling sequential data in applications such as natural language processing.
a more recent approach to
Graph transformers allow nodes to attend to all other nodes in graph, allowing for direct model- ing of long-range interactions, in contrast to GNNs. This allows them to avoid several limitations associated with local message passing GNNs, such oversmoothing (Oono & Suzuki| (2020), over- squashing (Alon & Yahav] [021] Topping et al. 2022), and limited expressivity (Morris et al. 2019]
Xu al. 2018). The promise of graph transformers has led large number of different graph transformer models that have been proposed in recent years (Dwivedi & Bresson 2020 Kreuzer al. 2021 Ying al. 2021 Mialon al., 2021). A major issue with graph transformers is the need to identily the location and structure of nodes within the graph, which has also led to a number of proposals for positional and structural encodings for graph transformers (Lim al. 2022).
One major challenge for graph transformers is their poor scalability, as the standard global attention mechanism incurs time and memory complexity of ((IV))) quadratic in the number of nodes the graph. While this cost is often acceptable for datasets with small graphs (e.g., molecular graphs), can be prohibitively expensive for datasets containing larger graphs, where graph transformer models often do not fit in memory even for high-memon GPUs, and hence would require much more complex and slower schemes to apply. Morcover, despite the expressivity advantages of graph transformer networks (Kreuzer et al.) 2021), graph transformer- based architectures have often lagged besssge-passing counterparts in accuracy in many practical settings.
A breakthrough came about with the recent advent of GraphGPS (Rampásek et al. 2022). modu-
lar framework for constructing graph transformers by mixing and matching various positional and structural encodings with local message passing and a global attention mechanism. To overcome

---

Under review as a conference paper at ICLR 2023
the quadratic complexity of the "dense" full transformer, they also incorporate "sparse" attention mechanisms, like Performer (Choromanski et al., 2021) or Big Bird (Zaheer et al. 2020). These sparse trasnformer mechanisms are attempt at improving the scalability. This combination of
Transformers and GNNs achieves state-of-the-art performance on a wide variety of datasets.
Despite great successes, the aforementioned works leave open some important questions. For instance, unlike pure attention- approaches (e.g., SAN, Graphormer), GraphGPS combines transformers with message passing, which brings into question how much of the realized accuracy gains are due to transformers themeselves. Indeed. Rampásek et al.]s ablation studies showed that the impact of the transformer component of the model is limited: on a number of datasets, higher accuracies can be achieved in the GraphGPS framework by not using attention at all (rather than, say, BigBird). The question remains, then, of whether transformers in their own right can obtain results on par with saassage-psssingg based approaches while scaling to large graphs.
Another major question concerns graph transformers' scalability. While BigBird and Performer are linear attention mechanisms, they still incur computational overhead that dominates the per-epoch computation time for moderately-sizer graphs. The GraphGPS work tackles datasets with graphs of up to 5,000 nodes, regime in which the full-attention transformer is in fact computationally faster than many sparse linear-attenee attention mechanisms. Perhaps more suitable sparse attention mechanisms could enable their framework to operate even larger graphs.
Relatedly, existing sparse attention mechanisms have largely been designed for sequences, which natural for language tasks but behave quite differently from graphs. From the ablation studies, BigBird and Performer are not as effective on graphs, unlike in the sequence world. Thus, is natural to ask whether one can design sparse attention mechanisms more tailored to learning interactions on general graphs.
Our contributions. We design sparse attention mechanism, EXPHORMER, that has computa- tional cost linear in the number of nodes and edges. We introduce expander graphs as a powerful primitive in designing scalable graph transformer architectures. Expander graphs have several desir- able properties - small diameter, spectral approximation of a complete graph, good mixing prop- erties which make them suitable ingredient are able to show that EXPHORMER, which combines expander graphs with global nodes and local neighborhoods, spectrally approximates the full attention mechanism with only a small number of layers, and has universal approximation properties.
sparse attention mechanism. As a result, we
Furthermore, we show the efficacy of EXPHORMER within the GraphGPS framework. That is, com- bining EXPHORMER with GNNs, helps achieve good performance on number of datasets, includ- ing state-of-the-ar results on CIFAR1O, MNIST, and PATTERN. On many datasets, EXPHOR MER is often even more accurate than full attention models, indicating that our attention scheme perhaps provides good inductive bias for places the model "should look," while being more efficient and less memory-intensive. Furthermore, EXPHORMER can scale to larger graphs than previously shown we demonstrate that pure EXPHORMER model can achieve strong results on ogbn-arxiv, a chal- lenging transductive problem on a citation graph with over 160K nodes and million edges, setting in which full transformers are prohibitively expensive due to memory constraints.
RELATED WORK
Graph Neural Networks (GNNs). Early works in the area of graph learning and GNNs include the development of number of architectures such as GCN (Defferrard et al.) 2016 Kipf / Welling 2017), GraphSage (Hamilton et al. 2017). GIN (Xu et al. 2018), GAT (Veličković et al. 2018). GatedGCN (Bresson & Laurent (017). and more. GNNs are based on a message-passing archi- tecture that generally confines their expressivity to the limits of the 1-Weisfeiler-Lchman (1-WL) isomorphism test (Xu et al. 2018).
A number of recent papers have sought to augment GNNs to improve their expressivity, For instance, one approach has been to use additional features that allow nodes to be distinguished - such as using a one-hot encoding of the node (Murphy et al. 2019) or random scalar feature [Sato et al. 202T or to encode positional or structural information of the graph e.g., skip-gram based network embeddings (Qiu et al. 2018), substructure counts (Bouritsas al. 2020), or Laplacian
2

---

Under review as a conference paper at ICLR 2023
eigenvectors (Dwivedi al. 2021). Another direction has been modify the message passing rule to allow the network to take further advantage of the graph structure, including the directional graph networks (DGN) of Beaimi et al. (202T) that use Laplacian eigenvectors to define directional flows that are used for anisotropic message aggregation, or to modify the underlying graph over which message passing occurs, higher-order GNNs (Morris et al. 2019) the use of substructures such as junction trees (Fey et al. 2020) and simplicial complexes (Bodnar et al., 2021).
Graph transformer architectures. Attention mechanisms have been extremely successful in se- quence modeling since the seminal work of Vaswani et (2017). The GAT architecture (Veličkovid al.) 2018) proposed using an attention mechanism determine how node aggregates informa- tion from its neighbors. It does not use positional encoding for nodes, limiting its ability to exploit global structural information. GraphBert (Zhang et al.) (020) uses the graph structure determine an encoding of the nodes, but not for the underlying attention mechanism.
Graph transformer models typically operate on a fully-connected graph which every pair of nodes is connected, regardless of the connectivity structure of the original graph. Spectral Attention Networks (SAN) (Kreuzer et al. 2021) make use of two attention mechanisms, one on the fully- connected graph and one the original edges of the input graph, while using Laplacian positional encodings for the nodes. Graphormer (Ying et al. (22T)) uses single dense attention mechanism but adds structural features in the form of centrality and spatial encodings. Meanwhile, Graphi'T (Mialon et al. 2021) incorporates relative positional encodings based on diffusion kernels.
GraphGPS (Rampásek et al. 2022 proposed general framework for combining
networks with attention mechanisms, while allowing for the mixing and matching of positional and structural embeddings. Specifically, the framework also allows for sparse transformer models like BigBird (Zaheer et al. 2020) and Performer (Choromanski et al. 2021).
Sparse Transformers. Standard (dense) transformers have quadratic complexity in the number of tokens, which limits their scalability to extremely long sequences. By contrast, sparse transformer models improve computational and memory efficiency by restricting the attention patter,, i.e., the pairs of nodes that can interact with each other. In addition to BigBird and Performer, there have been a number of other proposals for sparse transformers; Tay et al. (2020) provide a survey.
THE EXPHORMER ATTENTION MECHANISM
This section describes EXPHORMER, our sparse generalized attention mechanism that be used in individual layers of graph transformer architecture. We begin by describing graph attention mechanisms in general.
3.1 ATTENTION MECHANISM ON GRAPHS
An attention mechanism on tokens can be modeled by directed graph H on [m] (1. 2, ... n). where a directed edge from i to j indicates direct interaction between tokens i and j. i.e., an inner product that will be computed by the attention mechanism. More precisely, transformer block can be viewed as a function on the d-dimensional embeddings for each of n tokens, mapping from dx Rdd Let X (x1, X2.... ..) E Rdxa A generalized (dot-product) attention mechanism ATTNH RRdx + Rdxn with attention pattern given by H is defined by
ATTN (X). = + Σ Wy Wo a ((W2Xwarl)
(w2x:))
where h is the number of heads and m is the head size, while W K: W W E mmd and W E Rdxm_ (The subscript K is for "keys," Q for "queries," V for "values," and O for "output.") Here ( denotes the submatrix of X obtained by picking out only those columns corresponding to elements of NH (t), the neighbors of i in H. We can see that the total number of inner product [n]] is given by the number of edges of H. A (generalized) transformer
computations for all block consists of ATTN followed by a feedforward layer:
FF(X)= ATTN, (X) + We ReLU(W, ATTNE (X) b by1²) 12 T
3

---

Under review as a conference paper at ICLR 2023
(a)
(h)
(c)
(d)
Figure 1: The components of EXPHORMER: (a) shows local neighborhood attention, i.e., edges of the input graph. (b) shows an expander graph with degree 3. (c) shows global attention with a single virtual node. (d) All of the aforementioned components are combined into single interaction graph that determines the attention pattern of EXPHORMER.
where W1 Rx W2 E RRdx", b1 E R", and 22 E Rd.
In the standard setting, the tokens are part of sequence (e.g., language applications). However, we are concerned with the graph transformer setting in which the tokens are nodes of some underlying graph G = (V, E) with V = =[n]. The attention computation is nearly identical, except that one can also optionally augment it with edge features, is done in SAN (Kreuzer al. 2021):
Σ w W W XMMCo ((WLEMMO) xxx (waxi))
ATTN (X):s =x;
where W E E Rmmdd (emxde,ENz()) is the dg x (i)(1) matrix whose columns are dg-dimensional edge features for the edges connected to node i, and denotes element-wise multiplications.
The most typical cases of graph transformers use full (dense) attention, where every token attends every other node: H is the fully-connected directed graph. As this results in computational complexity (n?²) for the transformer block, which is prohibitively expensive for large graphs, we wish replace full attention with sparse attention mechanism, where H has o(n²) edges ideally, (n)).
number of sparse attention mechanisms have been proposed address the aforementioned issue (see Tay et al. 2020), but the vast majority are designed specifically for functions on sequences. EXPHORMER, on the other hand, graph-centric sparse attention mechanism that makes use of the underlying structure of the input graph G. As we will see, EXPHOR MER is perhaps most similar in design to the BIGBIRD architecture (Zaheer et al. 2020) designed for functions on sequences, but takes advantage of the underlying graph structure.
We can either use EXPHIRMER layers in a pure graph transformer model, or combination with message passing network using the GraphGPS framework.
3.2 THE EXPIORRMER ARCHITECTURE
We now describe the details of the construction of EXPHORMER, an expander-based sparse attention mechanism for graph transformers with O[[V] + El)) computation, where = (V, E) the under- lying input graph. The EXPHORMER architecture constructs an interaction graph H that consists of three main components, as shown in Figure [ The construction always has bidirectional edges, and so H can be viewed an undirected graph. The mechanism uses three types of edges:
1. Expander graph attention:
The main building block of our architecture is the use of edges from a random expander graph, described more detail shortly. These graphs have several useful theoretical properties related to spectral approximation and random walk mixing (see Section which allow propagating information between pairs of nodes that distant in the input graph G without connecting all pairs of nodes. In particular, use a regular expander graph of constant degree, which allows the number of edges to be just O().)). The process we use to construct random expander graph is described in Appendix
2. Local neighborhood attention: Another desirable property to capture is locality. Graphs carry much topological structure than sequences, and the neighhorhoods of individual
4

---

Under review as a conference paper at ICLR 2023
nodes carry lot of information about connectivity. Thus, model local interactions by allowing each node v to attend to every other node that is an immediate neighbor of v in G: that is, H includes the imput graph edges E as well their reverses, introducing ((EE) interaction edges. One generalization would be to allow direct attention within k-hop neighborhoods, but this might introduce superlinear number of interactions on general graphs
3. Global attention: The final component is global attention, whereby a small number of virtual nodes are added to the interaction graph, and each such node is connected to all the non-virtual nodes. These nodes enable global "storage sink" and help prove universality properties of EXPHORMER. We will generally add constant number of virtual nodes, in which case the total number of edges due to global attention will be O(IV)).
The model uses learnable embeddings for expander and global connection edge features, and virtual nodes features. Dataset edge features are used for the local neighborhood edge features.
Remark 3.1 EXPHORMER has some conceptual similarities with BigBird, as mentioned previously. For instance, we also make use of virtual global attention nodes, corresponding to BIGBIRD-ETC.
However, our approach departs from that of BigBird in some important ways. While BigBird uses w-width "window attention" capture locality of reference, we use local neighborhood attention to capture locality and graph topology. In particular, the interaction graph due to window attention in while EXPHORMER
BigBird can be viewed as a Cayley graph on Z, which sequence-centre graph-centric and, therefore, uses the structure of the input graph itself to capture locality. BigBird, as implemented for graphs by Rampássk el al. (2022), instead simply orders the graph nodes in an arbitrary sequence and uses windows within that sequence.
Both BigBird and EXPHORMER also make use of a random attention model. While BigBird uses an Erdös-Red Rényi graph |V] nodes, approach is to use a d-regular expander for fixed constant d. The astute reader may recall that a Erdōs-Rényi graph G(n,p) has spectral expansion properties for large enough p. However, it is known that p = nn
log is the connectivity threshold, iee, for
p (1 c) logn G(n.p) ) is almost surely disconnected graph. Therefore, in order obtain even a connected graph in the Erdös-Rényi Rényi model let alone one with expansion properties one would giving superlinear complexity for the number of edges. BigBird uses p (1//n), keeping a linear number of edges but losing expansion properties. Our expander graphs, by contrast, allow both a linear number of edges and guaranteed spectral expansion properties.
need p Ω log
We will see in the practical experiments of Section that EXPHORMER based models often substan- tially outperform BigBird-based equivalents, with Jewer parameters.
Remark 3.2 Previous graph-oriented transformers have, naturally, used the graph structure in their attention mechanisms. The SAN architecture (Kreuzer et al.) 2027) uses two attention mecha- nisms, one based on the input edges E and one based on all the other edges not present in the input graph. By using single atlention mechanism, EXPHORMERS introduce fewer additional parame- ters, allowing for more compact models that also significantly outperform SAN in our experiments.
THEORETICAL PROPERTIES OF EXPHORMER
MXP is based on expander graphs, which have a number of properties that make them suitable key building block of our approach. In this section, describe relevant properties of expander graphs along with their implications for EXPHORMERS.
4.1 BASICS OF EXPANDER GRAPHS AND LAPLACIANS
For simplicity, let us consider d- regullar graphs (where every node has d neighbors). Suppose G is d-regular undirected graph vertices. Let Ag be the n x adjacency matrix of G. It known An 2 -d. The graph G is said to be an
that Ag has n real eigenvalues d = X₁ > X > e-expander if max (1x2), } < (1 e)d Alon 1986).
5

---

Under review as a conference paper at ICLR 2023
Intuitively speaking, expander graphs sparse approximations of complete graphs. It is known that expanders have several useful properties (viz., edge expansion and mixing properties), which make the graph "well-comnected.. A higher corresponds to better expansion properties.
For example, in an expander graph, the diameter, (log n), is as low as possible for given number of edges without bottleneck cut (Alon 1986), which is defined as:
EnSx S (1 d|
4.2 EXPANDER GRAPHS AS APPROXIMATORS OF COMPLETE GRAPHS
We now outline some important properties of expander-based attention mechanism. Roughly speaking, our goal is to replace a densely connected graph, i.c., complete graph, with O(n²) edges by graph with on preferably Onn), edges that preserves certain properties of the complete graph. We show that suitable expander graphs, in fact, achieve this.
4.2.1 SPECTRAL PROPERTIES
useful tool study expanders the Laplacian matrix of a graph. Letting De denote the n diagonal matrix whose i-th diagonal entry is the degree of the i-th node, define LG Do - Ag to be the Laplacian of G. known that LG captures several important spectral properties of the graph. The first useful property of complete graphs that expander graphs (approximately) preserve the spectral decomposition the Laplacian - per this well known theorem spectral graph theory.
Theorem 4.1 A d-regular e-expander G on n vertices spectrally approximates the complete graph K,, on n vertices. i.e.] (1 (1-
1 La (1+ (I
Spectral approximation is known preserve the structure in graphs. As a result, replacing dense attention mechanism with a sparse attention mechanism along the edges of an expander graph retains spectral properties (viz., cuts, vertex expansion, etc.)
4.2.2 MIXING PROPERTIES
Another property of expanders is that random walks mix well. Let G E)) be d-regular expander. Consider a random walk up, U1, ...... on G, where vo is chosen according to an initial distribution π (0), and then each subsequent ut+1 is one of the neighbors of v, chosen uniformly at random. Then each v, is distributed according to the probability distribution (1) V - R++ given recursively by (t--1) D. (f)(1) turns out that after logarithmic number of steps, a random walk from starting probability distribution on the vertices is close to uniformly distributed along all nodes of the graph.
Lemma 4.2 Alon 1986
Let G (V, E) be d-regular e-expander graph on n = [V] nodes. For any initial distribution π 0) E+ and any ê 0, =(1)_ - + satisfies
(| 1/nl11 S 8,
as long as i 22 ( log(n/5)), i.e., the resulting distribution the nodes of G of random walk with walks starting from the distribution T(0) is 8-close L to the uniform distribution.
an attention mechanism i is connected to j if i and j attend to each other). If the attention mechanism is dense, then each node is connected to every other node and it is trivial to see that every pair of nodes interacts with each other in single transformer layer. In sparse attention mechanism, the other hand, some pairs of nodes are not directly connected, meaning that a single transformer layer will not model interactions between all pairs of nodes. However, if we stack transformer layers top of each
transformer, one can consider the graph of pairwise interactions (i.e.,
Notation: given matrices A and say that A < B if B is positive semi-definite matrix.

---

Under review as a conference paper at ICLR 2023
other, the stack will be able model longer range interactions. In particular, a consequence of the above lemma is that if our sparse attention mechanism is modeled after an e-expander graph, then stacking at least t = log(n/0 6) layers will model "most" pairwise interactions between nodes.
A related property concerns the diameter of expander graphs. One can, in fact, show that the diam- eter of regular expander graph is logarithmic in the number of nodes, asymptotically.
Suppose G = (V, E) is d-regular c-expander graph on verfices. Then, for every vertex y and k 2 0, the k-hop neighborhood ((v,r) = {w E V d(u, w) S k3 has
Theorem 4.3 (Alon 1986)
[B(u, 2 min((1 + +c)
for some constant c > 0 depending on d, In particular, we have that diam(G) = Os.e (log n))
As a consequence, we obtain the following result, which shows that using logarithmically many successive transformer layers allows each node to propagate information to every node.
Corollary 4,4 If a sparse attention mechanism on nodes is modeled as a d-regular e-expander graph, then stacking Od,e(logn) n) transformer layers models all pairwise node interactions.
4.3 EXPHORMER- SEAERMERR-BBEED TRANSFORMERS ARE UNIVERSAL. APPROXIMATORS
While the expander graph component EXPHORMER guarantees that (log 12) graph transformer layers are enough to allow each node to interact with every other node, it may still be desirable to enable node interactions with smaller number of layers (e.g., O n) can still be infeasible when the number of nodes, is extremely large). The global attention component allows this by essentially serving as a "short circuit" by which every node can interact with every other node using just two graph transformer layers.
The global attention component also helps us to obtain universal approximation property of Ex- PHORMER. In particular, continuous functions f [o, 1]dx[V] -> Rdx[V] can be approximated to desired accuracy by an EXPHORMER network as long as there is at least one virtual node. We defer the details to the appendix (see Appendix D).
5 EXPERIMENTS
In this section, we evaluate the empirical performance of graph transformer models based on EXPHORMER
wide variety of graph datasets with graph prediction and node prediction tasks [wwivedi et al. (2020); Hu et al. 2020); Freitas et al. (202T). We perform ablation studies on eight benchmark datasets. including image-based graph datasets (CIFARIO, MNIST), molecu- lar dataset (ogbg-moug mogggmollpbba, synthetic datasets (PATTERN, CLUSTER), and datasets based on code
graphs (ogbg-code2, MalnetTiny). We also demonstrate the use of EXPHIORMER on a large citation
Model
CIFARTO Accuracy
Tiny
MNIST
CLUSTER
PATTERN
Accuracy 1
Accuracy
Accuracy 1
Accuracy 1
GCN kint & Welling
2017
55.710++0.38
81.0
90.705+-.2188
68.498
71,892 + 0.
GIN Ku d. 2018
$5.255+11.50 527
88.98=0.5557
96.485:10.255
64.716 = 1.553
85.387 = 0. 136
GAT Velc
2018
64.223-t:.00 455
92.1 #0.242
05.5335+-..20 205
70.587 0.447
78.271 081
GatedOCK lroes & Losion 2017
67.3124+0.311
92.2331:0.65
97.340:10.114
73,840 = 0.326
85.568 : 0.088
PNCA Lono
70.35
97.94:10.12
DGN Beant er
72.838:100441
86.680-10.034
CRaW Togelsff dl
2021
69.013
97.944:100000
GIN-AKE Aww./K////ann Chan
72.19-40.13
86. 850--0000
SAN Kosuer al 2021
76.691:1.0.6
86.581 86.581110.037
K- KuSuhhapph SAtiummea
10271
77.856=0.1 104
86, 86.848810.00
EGT SGH SPH(+O) D0 finsain
60.604
97.722-10.222
77.909 0..00-00..... 0.245
86.730-10.036
GraphGPS Kamploak atll
02.298-+0.356
93,50-10.41
77.95:1-0.055
90.324-1-.132
EXPHORMER
72.884110.166
92.24-0.291
98.238 0.039
77.295 = 0.060
88.079110.104 90.522++0.030
MPNN+EXPIORMEE
74.754:10.194
93.16=0.137
98.414 0.038
78.024=0.041
Table 1:
Comparison of EXPHIRRMER with baselines on various datasets. Best results are colored in first, second, third.
7

---

Under review as a conference paper at ICLR 2023
Model
#Layers
Hidden layers
#Positional encoding
Expander degree
#Parameters
Time Epch/Total
Accuracy
GPS-MPNN: GatedGCN
52
LapPE
79.654
43s/1.18h
69.95 = 0.199
GPS: Transformer
52
LapPE
70,762
40s/1.1
68.86 = 1.138
GPS: Transfomerr MPNN
40
ESLapPE
111,735
104s/2.89h
73.53 = 0.236
GPS: Transformer + MPNN
52
LapPE
112.726
62s/1.72h
T2.31 = 0.311
GPS: Performer + MPNN
40
ESLapPE
283,935
132s/3.65h
70.18 0.095
GPS: Porformer + MPNN
52
LapPE
239,554
77s/2.141
70.67 = 0.338
GPS: BigBird + MPNN
40
ESLapPE
128,335
243s/6, 75h
70.51 + 0.256
BigBird
LapPE
129,418
145w/4h
0.106
EXPHORMER
44
ESLapPE
84,134
78kh
12.33 = 0.155
EXPHORMER EXPHORMER MPNN
44
ESLapPE
119,022
80s/2.23b
T2.88 = 0.166
40
ESLapPE
111,095
115s/3.21b
74.75 0.191
EXPHORMER +
133,819
114s/3.9h
75.03
0.186
Table 2: Results with varying attention and MPNNs on CIFARIO. EXPHORMER with MPNN pro- vides the highest accuracy. Also, pure transformer models based on EXPHORMER (without the use of MPNNs) are comparable.
network, ogbn-arxiv. A full description of the datasets is found in A Experiments for ogbn-arxiv have been performed on NVIDIA A100 GPUs, while all other experiments were on NVIDIA V100s.
5.1 COMPARISON OF EXPHIORMER-BASER MODELS TO BASELINES
We apply EXPHORMER to the modular GraphGPS framework (Rampásek et al. 2022), which constructs graph transformer models by composing attention mechanisms with schemes, together with choice of positional and structural encodings. We also show the results for pure attention EXPHIORMRR-OW results on five datasets from the Benchmarking GNNs collection (Dwivedi et al. 2020), along with MalNet-Tiny (Freitas et al. 2021). Using an EXPHORMER based graph transformer with message- passing in the GraphGPS tramework yields competitive results, including state-of-the-ari (SOTA) on three of the datasets. Notably, our EXPHORMER models outperform not only the MPNN base- lines but also recent full (dense) attention graph transformer models (i.e., SAN and full transformer models in the GraphGPS paper). Tables 2 and 3 show the EXPHORMER architecture have are sig- nificantly fewer training parameters but provide much better accuracy, suggesting that the structured sparsity in EXPHORMER can offer regularization advantages as well as time and memory scalability.
models that not use message passing network. Table|ssows
Table 5 (see Appendix B.I gives similar comparisons for two datasets from the OGB collection Hu et al. (2020): ogbg-molpeba and ogbg-code2. Our models are competitive with existing baselines. Our mildly worse performance on ogb-molpeha is perhaps not surprising, given that this a molec- ular dataset consisting of small graphs (an average of 26 nodes). On small graphs, the attention pattern in EXPHORMER is unlikely to be very different from that of the dense attention mechanism; thus the scope for us to improve is limited. Indeed, the greatest improvements from EXPHIORME are on datasets where the average number of nodes is larger, e.g., around 100 or more nodes.
5.2 COMPARISON OF ATTENTION MECIANNSSMS
We now discuss a series of experiments to isolate the performance of pure attention EXPHORMER model compared other attention mechanisms, which will help isolate the attention mechanism used in the model. For each dataset, we take our EXPHORMER--asee models and compare them to models obtained by replacing the EXPIIORMER attention mechanism with other dense (full trans- former) and sparse (BigBird, Performer) attention mechanisms. As different mechanisms can re- quire drastically different numbers of parameters, we train two models per mechanism: one which all hyperparameters are kept the same but vary the attention mechanisms; and another in which the hyperparameters are adjusted in order to keep the total number of parameters of the model roughly the same.
Results for the CIFARIO dataset are in Table 2 the other datasets are in the Appendix. EX- PHORMER-based GPS models (with both EXPHORMER attention and MPNNs) outperform com- parable models where the attention mechanism is replaced (by full attention or a sparse attention model such BigBird and Performer). Similar comparisons other datasets are in Appendix [B.) again, EXPHORMER outperforms other sparse attention mechanisms while either surpassing or per- forming comparably to full (dense) attention.
8

---

Under review as a conference paper at ICLR 2023
5.3 PURE TRANSFORMER ARCHITECTURES
The results presented thus far naturally lead to questions: (1.) how much of the performance gain of EXPHORMER-base GPS models is attributable to the attention component as opposed the MPNN component, and (2.) whether "pure" spurse transformer models can achieve good performance by itself. Indeed. Rampásck al. (2022) present ablation studies showing that removing the MPNN component from the proposed GraphGPS models results in significantly worse performance. Simi- larly, Kreuzer et al. (202T) offer two variants of their SAN architecture, the "full" variant that uses dense attention, as well as a "sparse" variant that allows nodes to attend only to direct neighbors in the input graph-their ablation results show that their "sparse" variant performs significantly worse than the "full" variant, often underperforming pure MPNNs.
In order to address these questions, we also train pure EXPHORMER- sparse transformer mod- els that use only attention without any message passing. The results for CIFARIO in Table 2 show that the pure EXPHORMER models (labeled "Exphormer"), in fact, outperform pure transformer GPS models well as most GPS models that use MPNNs. The main exception is the dense atten- tion "Pransformer+MPNN model; however our pure EXPHORMER model performs competitively. Similar comparisons other datasets are shown in Appendix B33
5.4 SCALABILITY TO LARGE-SCALE GRAPHS
One of the difficulties with graph transformer architectures has been their poor scalability to larger graphs with thousands of nodes. Dense attention mechanisms, like SAN and Graphormer, with quadratic memory complexity and time complexity restrict their applicability to datasets on graphs with a small number of nodes.
GraphGPS Rampásek et al. (2022) used sparse attention mechanisms but their architecture handles graphs of up to about 5,000 nodes, in MalNet-Ting -iny (Freitas et al. (021). Again, EXPHORMER- -based models provide improved accuracy, shown in Tables and 10
Our work allows us to extend graph transformer architectures to far larger graphs, with hundreds of thousands of nodes. We show that EXPHORMER architecture can scale, with competetive accuracy, to ogbn-arxiv (Hu et al. 2020). a transductive dataset consisting of a single large graph of the citation network of over 160K arXiv papers, containing over million edges. Specifically, we achieve test accuracy of 0.7196 using the EXPHORMER architectures. At the time of writing, a relevant leaderboard plrs 0.7637 the highest reported test accuracy, based adaptive graph diffusion networks (Zhao et al. 2021). Table 3 shows the relative performance of EXPHORMER compared to other Transformers. A dense full transformer does not even fit in memory on NVidia A100 GPU (even with only 2 layers and 32 hidden dimensions). The best accuracy for other sparse models was found with networks of 3 hidden layers and 96 hidden dimensions. Notice that BigBird and Performer have significantly longer epoch times and worse performance compared to EXPHIOMER with degree 3 expander edges.
Model
Accuracy
Epoch times
#Parameters
BigBird
55.19 + 0.16
16.745
296, 968
Performer
55.24 0.05
8.1905
276.808
EXPHORMER
71.51 1: 0.04
2.097
267.976
EXPHORMER-GCN
71.96 0.12
0.9652
268.264
Table 3: Comparison of attention mechanisms on the ogbn-arxiv dataset.
6 CONCLUSION
MER is new sparse graph transformer architecture built on expander graphs. We have shown that the relevant mathematical properties of expander graphs make EXPHORMER a suitable choice for graph learning, with time and memory complexity linear in the size of the graph. Using MER in the GraphGPS framework allows us to obtain state-of-the-art empirical results on number of datasets while also allowing graph transformers to scale to datasets on large graphs, realm which has proved elusive for graph transformers in the past.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-9) 96, 1986.
Noga Alon. Explicit expanders of every degree and size. Comb, 41(4))447-463, 2021. doi: 10. 1007/s00493-020-4429-x URL https::/doi. org.10..g11... 007 1 020-0000--00 4429-2
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL
net forum? did=
18COPhOCVH2
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning (ICML), pp- 748-758. PMLR, 2021.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Infor- mation Processing Systems, 34, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09223 2020.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets.
arXiv preprint
arXiv:1711.07553, 2017.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph rep- resentation learning. arXiv:2202.0300 2022.
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 J. Colwell, and Adrian Weller. Rethinking attention with per- formers. In 9th International Conference on Learning Repressentations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URLLttts:://ppeneww// 1d-Ua6zukOWRB
net forum?
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844 3852, 2016.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. CoRR, https/2012.999999 2020. URL
09699
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, abs/2003.00982, 2020. URL https://arxiv
axg/abs/2003..00 00982
Vijay Prakash Dwivedì, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875. 2021.
Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint 200i::2000./27779 2020.
Scott Freitas, Yuxiao Dong, Joshua Neil, and Duen Horng Chau. A large-scale database for graph representation learning. In Joaquin Vanschoren and Sai-Kit Yeung (eds.), Pro- ceedings of the Neural Information Processing Systems Track on Datasets and Bench- marks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual, 2021. URL
neerrr.errreeiiii.eeeeerer..rp.r cc/ wtt.errppp..ccppppe//222....111. http://550022rrr00000000accccaaa
roundl.
10

---

Under review as a conference paper at ICLR 2023
Joel Friedman. A proof of Alon's second eigenvalue conjecture. In Lawrence L. Larmore and Michel X. Goemans (eds.), Proceedings of the 35th Anmual ACM Symposium on The- ory of Computing, June 9-11, 2003, San Diego. CA, USA, pp. 720-724. ACM, 2003. doi: 10.1 00.1145/78054227886666 URL https::///// wttp:i..rg/1.... 1144 114577854422 780646)
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing
Systems, pp. 1025-10333 2017.
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. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tics Lin (eds.), Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URR.hhtps:///roooe Fb60d41 walaaaa667222732222222o
neur ips. wwtpppppe///2///aaaeeeeeppe Absttd00bbbtttttttc .ttml.ttt.l.....................
Md Shamim Hussain, Mohammed Zaki, and Dharmashankar Subramanian. Edge-augmented graph transformers: Global self-attention is enough for graphs. arXiv preprint arXiv:2108.03338, 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations (ICLR), 2017.
Devin Kreuzer, Dominique Beaini, William L Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. arXiv preprint arXiv:2106.0388) 038993 2021.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess E. Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. CoRR, ab3/2202.13013, 2022. URL
Alexander Lubotzky, Ralph Phillips, and Peter Samakk Ramanujan graphs. Comb. 8(3):261-21) 1988. doi: 10. 10.1007/BF021267999 URL //t::. /ttp:::::///ooo.o/1////// 1001///111.111111111 1ww011000001000770
Gregory A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51-60, 1988. ISSN 0555-2923.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. CoRR, abs/2106.05667,, 2021. URL nttps://arxiv.er
2106.05667
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 Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673 PMLR, 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. httpthtts////eeeeee///e
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pp. 459-467, 2018
Ladislav Rampásek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general. powerful, scalable graph transformer. CoRR, doi: 10.485550arxiv.2225.. 12454.. URL https: //doi. http:://d/o.o./.....
abs/2205. 12454, 2022.
48550/arXis

---

Under review as a conference paper at ICLR 2023
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341. SIAM, 2021.
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. CoRR, 066622009.06..2, 2020.
06732
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with Id convolu- tions on random walks. arXiv:2102.087788 2021.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In The Tenth International Conference Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https://openreviee net/ ffrummidd
70m JUjZRGZ-AA A
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp- 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2018.
Mingqi Yang, Renjian Wang, Yanming Shen, Heng Qi, and Baocai Yin. Breaking the expression bottleneck of graph neural networks. IEEE Transactions Knowledge and Data Engineering, 2022.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yar Liu. Do transformers really perform bad for graph representation? ArXiv, hass2106.052334 2021.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-see -o-uuueecc functions? In 8th International Conference Learning Representutions, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020a. URL
net/ www.ooiiduruueeeeeeeeeee Byx-BYXMON
Chulhee Yun, Yin Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. O(n) connections are expressive enough: Universal approximability of sparse transformers. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Bal- can, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020b. URL http:ss///roceeeinngsssooo neurips. cwwperipppcccppeepee pctpccccpccccc////////// hash/ htas://c22233300bbaaa34422223333
Abst html
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: Trans- formers for longer sequences. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, De- cember 6-1 2020, virtual, 2020.
33:
http:ippppccppppe//// htmi
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. CoRR, abs/2001. .05140, 2020.
12

---

Under review as a conference paper at ICLR 2023
Jialin Zhao, Yuxiao Dong, Ming Ding, Evgeny Kharlamov, and Jie Tang. Adaptive diffusion in graph neural networks. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 23321 2021. wRw.ttss: pttpttpeps//ppoceedddeee ngs neurips.. cce AAstraa
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.
13

---

Under review as a conference paper at ICLR 2023
A
DATASET DESCRIPTIONS
Below, we provide descriptions of the datasets which conduct experiments.
CIFARIO and MNIST CIFARIO and MNIST are the graph equivalents of the eponymous image classification datasets. A graph created by constructing the 8-nearest neighbor graph of the SLIC superpixels of the image. These are both. 10-class classification problems.
CLUSTER and PATTERN PATTERN and CLUSTER are node classification problems. Both are synthetic datasets that are sampled from the Stochastic Block Model (SBM), which is a popular way to model communities. In PATTERN, the prediction task is identify if node belongs to one of the 100 possible predetermined subgraph patterns. In CLUSTER, the goal is to identify the cluster which a node belongs to, when the nodes are selected from 6 different clusters with the same distribution.
MalNet-Tiny Malnet-Ting Tiny a smaller dataset generated from a larger dataset for identifying mal- ware based on function call graphs. The dataset contains the call graphs from the Android APKs. The tiny dataset contains 5000 graphs. The graphs can have up to 5000 nodes. The task predict the graph being benign from one of four types of malware.
ogbg-code2 The ogbg-code2 dataset has the abstract sytax trees (ASTs) of python methods curated from github. The prediction problem is "code sumarization". To determine the name of a function given the body of the method.
ogbg-molpcha ogbg-molpehe is molecular datasets. It has graphs representing molecules, where the nodes and edges represent the atoms and their chemical bonds, respectively. The node features include atomic number, chirality etc. The goal is to predict binary labels. The dataset is heavily skewed as only only 1.4% of data has positive labels.
ogbn-arxiv The ogbn-arxiv dataset consists of large directed graph of 169343 nodes and 1, 1,166,243 edges representing a citation network between all computer science papers on arXiv that were indexed by the Microsoft academic graph. Nodes in the graph represent papers, while a di- rected edge indicates that a paper cites another. Each node has an 128-dimensional feature vector derived from embeddings of words in the title and abstract of the underlying paper. The prediction task is 40-class node classification problem to identify the primary category of each arXiv pa- per, listed by the authors. Moreover, the nodes of the citation graph are split into 90K training nodes, 30K validation notes, and 48K test nodes.
Table shows a summary of the statistics of the aforementioned datasets.
Table 4: Dataset statistics
Dataset
Graphs
Avg, nodes
Avg, edges
Prediction Level
No. Classes
Metric
MNIST
70,000
70.6
gruph graph
Accuracy
CIFAR1O
60.000
117.6
941.1
10
Accuracy
PATTERN
14,000
3,039.3
inductive node
Accuracy
CLUSTER
12,000
117.2
2,150,9
inductive node
Accuracy
ogbg-molpcbu
437,929
26.0
28.1
graph
128
Avg. Precision
ogbg-code2
452,741
125.2
124.2
graph
5 token sequence
Fl score
MaiNet-Tiny
5,000
1,410.3
2,859,9
Accuracy
ogbn-arxiv
169,343
1,166,243
node
Accuracy
B MORE EXPERIMENTAL RESULTS
B. BENCHMARKS OGB DATASETS
In Table 5 we show the results for OGB datasets (see the discussion in Section 5.1
14

---

Under review as a conference paper at ICLR 2023
Model
ogbg-molpcha Avg. Precision
ogbg-code2 FI
GCN+virtual node
0.2424 0.0034
0.1595 0.0018 0.1581 # 0.0026
GiN-viruual node
0,2700 # 0.0023
GatedGCN S-PE
0.267 0.002
PNA
0,2838 0.0035
0.1570 + 0.0032
DeeperGCN
0.2781 0.0038
DAGNN
0.1751 0.0049
DGN
0,2885 0.0030
GIN-AK+
0.2930 0,0044
CRaWi
0,2986 * 0.0025
ExpC Yang al. 2022
0,2342 0.0029
SAN
0.2765 0.0042
GraphTruns (GCN-Vinual)
0.2761 = 0.0029
0.1830 + 0.0024
K-Subtree SAT
0,1937 0.0028
GraphGPPS
0.2907 0.0028
0.1894 a: 0.0024
MPNN Exphorner
0.2823 = 0.0004
0,18507 0.047
Table 5: Comparison of EXPHORMER with baselines various datasets from the Open Graph Benchmark (OGB) (Hu et al. 2020)
B.2 HYPERPARAMETERS
Our hyperparameter choices, including the optimizer, positional encodings, and structural encod- ings, were guided by the instructions in GraphGPS (Rampásek et (022).. There were some cases, however, when more layers with smaller dimensions gave better results EXPHORMER. This may be due to the fact that each node gets fewer inputs for each layer, but EXPHORME requires more layers in order to propagate well. Additionally, we observed that Equivstable Laplacian Positional Encoding (ESLapPE) performed better than normal Laplacian Positional Encoding (LapPE). In our experiments, consistently replaced LapPE. For the GPS models with Exphormer, we consistently GatedGCN except for the ogbn-arxir dataset, which use GCN.
Through our model, some extra hyperparameters are introduced - the degree of the graph expander and the number of virtual nodes. For these hyperparameters, used linear search and found that expander degree 3-5 was the most effective. Depending on the graph size, we used 1-5 virtual nodes.
To make fair comparisons, CLUSTER, we used a parameter-budge of 500K, and for CIFAR and MNIST, we used a parameter- budget of around 100K. See details in Table and Table g
used similar parameter-budger
GraphGPS. For PATTERN and
Hyperparameter
CIFAR10
MNIST
MalNet-Tiny
PATTERN
CLUSTER
Num Layers
5
16
Hidden Dim
40
40
64
84
48
Num Heads
8
Dropout
0.1
0.1
0.15
0.0
0.0
PE
ESLapPE
ESLapPE
None
ESLapPE
ESLapPE
Batch Size
16
16
32
16
Learning Rate
0.001
0.001
0.0005
0.001
0.00001
Num Epochs
150
150
150
100
100
Expander Degree 5
5
5
5
5
Num Virtual Nodes
5
Num parameters
111,095
111,015
285,071
297,280
502,102
Table Hyperparameters used for GPS model using EXPHORMER for datasets: CIFARIO, MNIST, MalNet-Tiny, PATTERN, CLUSTER.
B.3 FULL COMPARISON OF ATTENTION MECHANISMS
In Section 5.2 presented two approaches for the comparison of models trained using different attention mechanisms fixing the hyperparameters and fixing a budget on the total number of trainable parameters. The results showed the advantage of EXPHORMER over other attention mech-
15

---

Under review as a conference paper at ICLR 2023
Hyperparameter
oghg-molpcha
ogbg-code2
Num Layers
5
4
Hidden Dim
40
256
Num Heads
4
Dropout
0.2
0.2
PE
RWSE
ASTNode
Batch Size
512
Learning Rate
0.0005
0.0001
Num Epochs
100
Expander Degree
5
Num Virtual Nodes
5
0
Num parameters
9,742.960
12,453,298
Table 7: Hyperparameters used for GPS model using EXPHORMER for datasets: ogbg moolmba, ogbg-code2.
Hyperparameter
CIFARIO
MNIST
MalNet-Tiny
PATTERN
CLUSTER
Num Layers
7
7
16
Hidden Dim
44
44
64
84
48
Num Heads
4
4
4
4
8
Dropout
0.1
0.1
0.15
0.0
0.1
PE
ESL
ESLapPE
None
ESLapPE
ESLapPE
Batch Size
16
32
16
Learning Rate
0.001
0.001
0.0005
0.001
0.001
Num Epochs
150
150
150
100
150
Expander Degree
5
Num Virtual Nodes
1
5
2
Num parameters 119,022
127,698
285,071
273,757
344,214
Table 8: Hyperparameters used for EXPHORRME model (without MPNN) for datasets: CIFARIO. MNIST, MalNet-Tiny, PATTERN, CLUSTER.
anisms for CIFARIO (Table 2 and PATTERN (Table 11 Here, we present similar results for the
remaining datasets MNIST Table MALNET-Thm my Table TO PATTERN Table I1 and
CLUSTER in Table 12
Model
#Layers
Hidden layers
#Positional encoding
Expander degree
#Parameters
Time
Accuracy
Epoch/Total
GPS: Transformer + MPNN
5
40
ESLapPE
111.655
131s/5.45h
98. 336 = 0.0189
GPS: Transformer MPNN
52
TapPE
115,394
76s/2.13h
98.051
0. 0.126
GPS: Performer + MPNN
40
ESLapPE
283,855
156w6.52h
98.34
0.0349
GPS: BigBird MPNN
EST ESP
128,255
267s/11.11h
98.176
0.0148
EXPHORMER
5
44
ESLapPE
92,146
75s/3.14h
98.08 = 0.051
EXPHORMER
7
ESLapPE
127,698
93s/3.87h
238
0.0387
EXPRORMER MPNN
5
40
ESLapPE
111.015
132x/5.99h
98.414 0.035
EXPHORMER MPNN
ESLapPE
133,731
137s/5.72h
98.424 0.018
Table 9: Ablation studies results for MNIST
B.4 EFFECT OF DIFFERENT COMPONENTS OF THE MODEL
[In the final version, this section will include similar analyses of more datasets.]
Here we analyze the effect each the components of the model. Our Exphormer model has three main components: local neighborhood, expander edges, and virtual nodes. In Table [3] we that removing each component leads to poorer results. The effect of local neighborhood edges is much more important in Exphormer models that do not include MPNN, suggesting that local
16

---

Under review as a conference paper at ICLR 2023
Model
#Layers
Hiddlnn layers
Positional encoding
Expander degree
#Paarameters
Time Epoch//ootal
Accuracy
GPS-MPNN: GateGGCN
64
199,237
6J/0255h
92:23 + 0.65
GPS: Performer
64
421,957
41s/1.73h
73.90
0.58
GPS: Transformer MPNN
64
282,437
94s/3.944
93.50
0.41
GPS: Performer MPNN
64
527.237
46x/1.
92.64
0.78
GPS: BigBird MPNN
64
324,357
1306/5 43h
92.34 1: 0.34
EXPRORMER
5
80
283,
15.22/11.555 05h
92.18 0.292
EXPHORMER
64
296,325
35, 2s/1 .7hh
92.24 #: 0.291
EXPRORMER MPNN
64
285,70
1..h
16 0.137
Table 10: Ablation studies results for MalNet-Tiny, The model marked with did not fit in memory with batch size 16, and was trained with batch size
Model
Hidden dimension
#Positional encoding
*Parameters
Time Epoch/Total
Accuracy
Transformer MPNN
84
ESLapPE
297.196
90.313
GPS: Transformer MPNN
64
LapPE-10
337,201
90.324
0. 132
GPS: Perforee++ MPNN
ESLapPE
469,816
86.571
0.114
GPS: Performer + MPNN
56
ESLapPE
267,740
86, 154
+ 189
GPS: BigBird MPNN
84
ESLapPE
340,258
260
0.167
GPS: BigBind MPNN
76
ESLapPE 279,304
90.446
0.047
EXPHORMER MPNN
ESLapPE
297,280
Table 11: Ablation studies results for PATTERN
and structural encodings are not fully sufficient to capture the structure of the graph and cannot be replace the actual edges.
Table 14 shows the effect of the degree of the expander graph. Selecting the right expander degree is important; results can vary lot for different expander degrees.
Table 15 shows a similar study on number of virtual nodes.
C DETAILS OF EXPANDER GRAPH CONSTRUCTION
major component of EXPHORMER the of the edges of expander graph. Thus far, have not specified which expander graph to use. In this section, we provide details of the specific expander graphs we use as well and quantify their spectral expansion properties.
C.I RAMANUJAN GRAPHS
A natural question is how strong the spectral expansion properties of a d-regular graph can be, i.e., for how large an > does d-regular c-expander exist. The following theorem gives bound on how large the spectral gap can be.
Theorem C.1 (Alon-Boppana) Let d > O. The eigenvalues of the adjacency matrix of d-regular graph on n nodes satisfy
max([>el 2 2
In other words, d-regular c-expander graph can exist only for 11 2 (1).
Model
#Layees
Hidden layers
#Pusitional
#Parameters
Time
Accuracy
encoding
Epoch/Total
GPS: Transfomerr MPNN
16
48
LapPE-10
502.054
77.95 1: 0.305
GPS: Performer MPNN
ESLapPE
1,927.510
78.339
GPS: Performer MPNN
48
ESLapPE
486,346
75.91 0.01
GPS: BigBird MPNN
ESLapPE
77.217
GPS: BigBird MPNN
16
40
ESLapPE
406,262
77.212 0.089
EXPHORMER MPNN
ESLapPE
78.024
Table 12: Ablation studies results for CLUSTER
17

---

Under review as a conference paper at ICLR 2023
Dataset
Model
No Neighborhood
Expander Edges
Connections
Components
Exphormer
61.91 0.199
0.205
72.33 0.153
Cifar10
Expborncr+MPAN
71.15 = 0.143
71.53 0.189
71.57 = 0.183
74.75 = 0.194
Table 13: Results for the full model versus removing each of the components. Each component helps the final model.
Expander Graph Degree
Datasct
Model
3
Exphormer
71.36 0.215 71.32
0.243
72.33 0.155 71.91 + 0.272
71.96 0.264
Catar10
Exphormer+MPNN
74.57 + 0.143 74.10 #: 0.122
74.75 + 0.194 74.54 + 0.296
74.70 + 0.226
Effect of the selection of the expander degree the results. We can that correct selecton of the expander degree does affect the quality of the final model.
Table 14:
As it turns out, there exist e-expander graphs with achieving this bound. fact, a d-regular e- expander graph satisfying 2 2v0-I is known Ramanjjan graph. Ramanujan graphs are essentially the best possible spectral expanders, and several constructions have been considered over the years (Lubotzky et al. 1988 Margulis 1988).
C.2 RANDOM REGULAR GRAPHS
While there exist deterministic constructions of Ramanujan graphs, they are often algebraic/number theoretic in nature and therefore exist only for specific choices of d (e.g., the constructions of Lubotzky et al. (188) as well as independently of Margulis (1988), for which one requires d (mod 4) and
be prime). Recently, the work of Alon (2021) showed a construction of strongly explicit near-Ramanujan graphs of every degree, but it should be noted that the construc- tion needs the number of nodes be sufficiently large. It is, therefore, often convenient use probabilistic construction of an expander.
natural choice for expander graph a random d-regular graph on n vertices, formed by taking d/2 independent uniform permutations on {1, .1,2....,. Friedman (2003) proved conjecture of Alon, establishing that random regular graphs are weakly- Rananujja
Theorem C.2 (Friedman 2003) Fix O and an even integer d > 0. Then, suppose G is random graph generated by taking independent uniformly random permutations 1 T2. R. on V 11, n.,, then choosing the edges as
E = (i, (i, ,, (0) :1sssiiiiiii
Then, with probability On (R(d),, G is 2d-regular graph and X(G) & /2d-1+c
d
In our experiments, we use a random regular graph to instantiate the expander graph component of EXPHORMER. We describe the details below.
Generating Random Regular Expander Let G = (V. E) be the original graph, where
V == (1,2,.... ...... Inspired by the expansion properties of the random graph process analyzed in Friedman (2003) (see Theorem C.2 we generate random regular graph G' E') on the same node set as follows.
Let = 11,
.n), .......... where each value appears d times. Pick random permutation on (1, nd), chosen uniformly at random from (nd)! possible permutations.
... ,, .7.
Let E' be the multiset {(s; (x())
nd).
Remove any self loops from E"; for large this will happen with probability o(1).
If X(G) & V2d-I+e then stop; otherwise generate a new random permutation т and try again.
18

---

Under review as a conference paper at ICLR 2023
#Virtual Nodes
Datasel
Model
4
Exphoemer
72.33 = 0.155
70.92
0.176
71.25
0.219
Cifar10
Exphormer+MPNN
74.75 + 0.194
74.19 0.177
71.38 = 0.145
74.53 # 0.22
Table 15: Comparing the effect of the number of the virtual nodes on the final result. Adding more virtual nodes sometimes is beneficial, but also sometimes can make the model overfit and makes less generalizable.
is easy to see that this procedure equivalent to sampling d permutations, so Theorem C.2 shows that the resulting graph will be 2d-regular expander with high probability.
D UNIVERSALITY OF EXPHORMER
In this section, we detail the universal approximation properties of EXPHORMER-basce graph trans- formers.
One of the limitations standard message passing networks is that their expressivity is generally confined by the limitations of the WL hierarchy. In other words, they cannot distinguish pairs of non-isomorphic graphs that cannot be distinguished by suitable WL test.
On the other hand, transformer architectures have the ability to distinguish any graphs
The work of Yun et al. 2020a) showed that for sequences, transformers are universal approximators, iee. they can approximate any permutation equivariant function mapping one sequence another arbitrarily closely when provided with enough parameters. A function f : |gdxn + Rddx is said be permutation equivariant if f(XP) f(X),, i.e., if permuting the columns of an input X E ddx= results in the columns of f(X) being permuted the same way.
Theorem D.1 (Yun et al. (2020a)) Let p and O. For any function f Rddx Rdxx that is permutation equivariant, there exists a transformer network g such that 8 (f.g)) <e
The same work shows extension to all (not necessarily permutation equivariant) scquence-to- sequence functions that are defined on a compact domain, say, [0, ddx provided that one uses a positional encoding. More specifically, for any transformer g Raxn ddx one can define transformer with positional encoding 9p Rdxn + Rd such that 9p = g(X + E). The following results shows that trainable positional encodings allow a transformer approximate any continuous function on the compact domain.
and 0. For any continuous function f: (0,1]dx + Rax= that is permutation equivariant, there exists a transformer with positional encoding gr such that ( (P, .) <
Theorem D.2 YYun et al. (2020a)) Let 1 S
Note that the above theorems hold for full (dense) transformers. However, under certain conditions about the sparsity pattern, one can obtain similar universality for sparse attention mechanisms (Yun) ct al. 2020b).
One important consideration is that the aforementioned results hold for functions sequences. Since we are concerned with functions on graphs, is interesting to ask what the implications are for graph transformers.
We follow the approach of Kreuzer et al. 2021): Given a graph G, we can view a node transformer function from x RX which uses the padded adjacency matrix of G positional encoding. Similarly, an edge transformer takes as input a sequence (ii.j), os.g) with i, E [r]] and i < such that oi.j 1 if i and are connected in G ojj = 0 otherwise. Any ordering of these vectors corresponds to the same graph. Moreover, we can capture the relevant functions going from R N(N-11/222 + IR 11/2xx2 with permutation equivariance. Ideally, they can be approximated closely desired by suitable transformers on the edge input.
Now, simply observe (see Kreuzer et al. (22T)) that one can choose a function (in either the node transformer edge transformer case) that is (a.) invariant under node permutations and (b.) maps
19

---

Under review as a conference paper at ICLR 2023
non-isomorphic graphs to distinct values. We would like to apply one of the above thoerems such a function.
However, cannot quite apply Theorem D.1 or Theorem D.2 is specifically for full transform- ers in which all nodes are pairwise connected in the attention interaction graph. The final ingredient require is theorem from Zaheer al. (2020), which gives universality theorem for sparse transformers on sequences.
Theorem D.3 Zaheer et al. (020)) Let < 0o and > 0. For any graph H on [n] that contains the star graph, we have that f E [0.1] + Rnxd is continuous function, then there exists a sparse transformer network g (with trainable positional encodings) such that E (f(.)) < e.
Now, combining D.3 with the previous observations and noting that EXPHORMER with at least one virtual node contains the star graph, we see that EXPHORMER can approximate solutions to the graph isomorphism problem (note, however, that this does not imply polynomial time solution to the problem, as in Kreuzer al. (202T).
20


Reviews:
[{"review_id": "MoMce54y_0", "reviewer": "Reviewer_U7gQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a new and scalable graph Transformer, named Exphormer. The motivation of this work is that existing graph Transformers can not efficiently scale to large graphs. Exphormer designs a sparse attention mechanism that consists of three main components: expander graph attention, local neighborhood attention and global attention. As the main building block, expander graph attention utilizes the edges of a regular expander graph with a constant degree in the interaction graph, thus allowing it have a linear computational cost. The authors further provide theoretical analysis of expander graphs and the implication with Exphormer. Extensive experimental results demonstrate the effectiveness of the proposed Exphormer.  ", "summary_of_the_review": "The method and theoretical analysis look good, but the experimental analysis, comparisons and writings need to be improved. ", "strength_and_weaknesses": "Strengths: \n-\tComparing with full-attention graph Transformers, Exphomer can perform sparse attention mechanism on larger graphs and efficiently reduce the computational cost.\n-\t The paper provides plenty of theoretical analysis to support their claims, although I have some concerns.\nWeaknesses:\n-\tFor two graphs with the same number of nodes, using the same degree constant may generate the same regular graphs, thus preserving the same edges.  How does this help in learning the features of the two graphs? In fact, the paper doesn’t distinctly illustrate the function of expander graph attention for learning node representations.\n-\tThe degree of regular graphs, d, is an important hyperparameter and graphs of different sizes may need different d, especially on large graphs. However, the parameter studies of d on different graphs are missing.\n-\tLacking of ablation studies to verify the effectiveness of the three main components of Exphormer. I’m curious about how much performance gain can expander graph attention bring.\n-\tMore experiments need to be conducted on large graph benchmarks (Citeseer, Pubmed, Computer, ogbn-proteins, etc.) to validate the effectiveness and scalability (especially the comparison of time and memory cost) of the proposed method on large graphs. In addition, existing sparse attention methods (GT[1]) and sampling-based methods (NAGphormer[2], Gophormer[3]) shall be chosen as baselines on large graphs.\n-\tThe paper is not very easy to follow and some notations are confusing. And the formulas are not numbered. Specifically, the format of Table 1 is totally a chaos and need to be reorganized.\n\n[1] Dwivedi V P, Bresson X. A generalization of transformer networks to graphs[J]. arXiv preprint arXiv:2012.09699, 2020.\n[2] Chen J, Gao K, Li G, et al. NAGphormer: Neighborhood Aggregation Graph Transformer for Node Classification in Large Graphs[J]. arXiv preprint arXiv:2206.04910, 2022.\n[3] Zhao J, Li C, Wen Q, et al. Gophormer: Ego-Graph Transformer for Node Classification[J]. arXiv preprint arXiv:2110.13094, 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IPD5pNPfEi", "reviewer": "Reviewer_X95y", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes Exphormer, a framework to improve the performance and scalability of graph transformers. Exphormer consists of three components, including expander graph attention, local neighborhood attention and global attention. The key innovation of this work is that Exphormer introduces expander graphs on graph transformers as a graph data augmentation method, which has rich theoretical properties. Meanwhile, Exphormer uses a sparse attention technology similar to BigBird, which reduces the quadratic time complexity of self-attention, making it possible to use it on larger-scale data. The authors demonstrate the abality and efficiency of Exphormer from two aspects of theoretical and experimental analysis, and achieves sota results on three datasets.", "summary_of_the_review": "This work combines graph transformers and expander graphs together, and uses sparse attention mechanism to reduce quadratic time complexity. However, the motivation of using graph transformers and expander graphs is insufficient, and the lack of large-scale dataset experiments is not convincing.", "strength_and_weaknesses": "Strengths:\n1. Nice English writing and clear sentences.\n2. The figure provides a good overview of the method.\n3. The theoretical analysis of expander graphs is solid and complete.\n4. Compared to other graph transformers, Exphormer has significant advantages in computational time complexity.\n\nWeaknesses:\n1. Insufficient motivation of using graph transformers as encoders. In the formula of the generalized (dot-product) attention mechanism at the bottom of page 3, each node only calculates attention scoers with its own 1-hop neighbor nodes. Such an attention process is not much different from the graph attention network (GAT), and destroys the properties of the global receptive field of graph transformers, which is a key advantage of graph transformers towards GNNs. There seems no problem if the graph transformer here is replaced with GAT, so the motivation of using graph transformers as encoders is not sufficient.\n2. The authors discuss in section 4.2.2 that if a certain number of transformer layers are stacked, the global receptive field of the Exphormer can be recovered. However, this method is common in GNN. Besides, the authors mention in the introduction that the stacking can lead to problems such as oversmoothing and oversquashing. It is mentioned above that the graph transformer in Exphormer is not very different from GAT, so will Exphormer also face the problems of oversmoothing and over squashing if stacking multiple layers?\n3. The authors mention in the introduction that most of the experiments done by GraphGPS focused on small graphs, but this work only conducts experiments on one large dataset, ogbn-arxiv. A key advantage of Exphormer is scalability, so it needs to be supplemented with more node classification experiments on other large-scale graph datasets.\n4. Theorem 4.1 analyzes the  approximation properties of expander graphs to complete graphs, but complete graphs are only a kind of special structures, which cannot represent the approximation propertities for general graph structures, and it seems there is no proof for this theorem. Besides, $S$ in equation 1 has no annotation, $\\pi^{(t+1)}=D_{G}^{-1}A_{G}\\pi^{(i)}$ in section 4.2.2 should be replaced with $\\pi^{(t+1)}=D_{G}^{-1}A_{G}\\pi^{(t)}$.\n5. In Appendix D, the authors analyze the universal approximation properties of Exphormer. However, the authors only uses the global attention module. It seems that expander graph attention and local neighborhood attention modules do not contribute to the theoretical performance of the model.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "35PZKL5E1M", "reviewer": "Reviewer_4gAE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a new attention mechanism for graph transformers aiming at handling graphs with large number of nodes.\n\nMore precisely, the attention mechanism is three-fold:\n- Local attention, applied to 1-hop neighbors of a given node.\n- Global attention via virtual nodes.\n- Sparse attention based on an expander graph, which is the main contribution of the paper.\nThe main model is used within GraphGPS framework, which combines an attention scheme with message passing and positional/structural encodings.\n\nThe authors motivate the use of an expander graph based attention by the theoretical properties of expander graphs: \n- The expander graph is a good approximation of the complete graph.\n- Random walks on the expander graph mix well, meaning that provided there are log(nb_nodes) expander graph attention layers, each node is able to communicate with any other node.\n\nThe author then proceed to experimentally demonstrate the benefits of the proposed attention mechanism over various GNNs and Graph Transformers, both in terms of accuracy and number of parameters/scalability. Finally, some ablations are conducted i) by combining other attention schemes than Exphormer with MPNN and ii) by comparing Exphormer without message passing to models that do not necessarily use message passing.", "summary_of_the_review": "This work offers a sensible solution, a sparse attention scheme relying on expander graphs, to an important problem, scaling graph transformers to large graphs. Expander attention has theoretically suitable properties and the experiments demonstrate that its combination to other attention mechanisms within GraphGPS framework scales to large graphs with reasonable performance in terms of accuracy.\n\nHowever, it seems to me that the paper stresses on the mathematical motivation of expander attention without studying whether these properties are indeed useful in practice, and the results on ogbn seem to be behind other baselines.\n\nTherefore, I do not recommend acceptance for now. I am willing to increase my score if my concerns (clarification of usefulness of expander attention, discrepancy with GNNs on ogbn-arxiv and with GraphGPS on ogbn-molpcba and ogg-code2) are answered.", "strength_and_weaknesses": "Strengths:\n- Scaling competitive graph transformers to large graph is an important problem for which this work offers a potential solution.\n- This work proposes interesting motivations for the use of expander graphs.\n- The proposed mechanism scales to larger graphs (order of magnitude of 100k nodes).\n- Some ablations demonstrate the usefulness of Exphormer compared to other graph transformers. More generally, the experimental protocol is thorough (error bars, various baselines and tasks).\n\nWeaknesses:\n- Although the use of expander graph is motivated, it is not clear whether these motivations are responsible for the performance of Exphormer: there is to my understanding no ablation on the role of each of the three attention mechanisms (local, global, expander), and the attention pattern could be studied to check whether expander attention indeed uses communication between distant neighbors.\n- Experiments on ogbn may be more convincing: experiments on arxiv are behind GAT, and behind GraphGPS for molpcba and code2. Moreover, it would be useful to display the results of Exphormer only on molpcba and code2.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-jzCfRD1j9W", "reviewer": "Reviewer_eDs8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new sparse attention mechanism for graph-structured data to address the quadratic complexity issue of graph transformers. Inspired by the idea of the sparse attention module BigBird for sequences, the proposed method, named Exphormer, also constructs an interaction graph based on three types of edges for attention. These edges include a random expander graph (random attention), the original graph (local neighborhood attention), and edges between any node and a virtual node (global attention). Thanks to the fruitful mathematical properties of expander graphs, the authors prove mixing properties and a universal approximation property of Exphormer. The authors show the first time that BigBird-like models, namely Exphormer, achieve very good performance on five graph benchmark datasets.", "summary_of_the_review": "This work successfully extends BigBird to graph-structured data and demonstrates the first time that BigBird-like sparse attention achieves SOTA performance on several graph classification datasets. I have some concerns about its insufficient experimental results on large-scale graphs, limited task types considered, and some missing experiments relative to hyperparameters and memory usage.\n\nOverall, I think the strong points overweight the weak points and I recommend a weak accept. I would further increase my score if all my concerns and questions are answered.", "strength_and_weaknesses": "##### Strengths\n1. The idea of using expander graphs (specifically d-regular expanders for fixed d) as a sparse approximation of complete graphs is elegant and original to my best knowledge.\n2. The proposed method seems to be simple to implement and to incorporate into existing framework combining transformers and GNNs, which only requires a sampler for generating random regular expander.\n3. The empirical comparison is fair and solid.\n4. The paper is well-written and easy to follow.\n\n##### Weaknesses\n1. (Positioning) This work is motivated by the fact that most existing graph transformers are limited to small graphs due to the quadratic complexity of full dot-product attention. However, the conducted experiments are somewhat misleading as most of the results are only shown on datasets of small-scale graphs. Given marginal improvements over the previous SOTA transformer GraphGPS that used either full or linear attention (e.g. Performer), the impact of this method is not very clear. On the other hand, for the more interesting tasks with large-scale graphs like ogbn-arxiv, the paper only shows very preliminary results, far behind the SOTA results. I expect a thorough evaluation of Exphormer on more datasets with large-scale graphs, such as other node classification datasets of OGB.\n2. (Limited task types) Exphormer is only evaluated on classification tasks. It would be more convincing to demonstrate the effectiveness of Exphormer on graph regression tasks.\n3. (Missing experiments) Some important studies of hyperparameters are missing, including the effect of expander graph degrees, the effect of the number of virtual nodes. It would also be useful to show the memory usage of the vanilla transformer, BigBird, Performer, and Exphormer.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject