Even Sparser Graph Transformers
Authors: Hamed Shirzad
Honghao Lin
Balaji Venkatachalam
Ameya Velingker
David Woodruff
Danica J. Sutherland
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Transformers
Expander Graphs
Sparsification
Primary area: graph_neural_networks
TL;DR: Attention scores on graphs are consistent across network widths; find which edges matter with a narrow network first

Abstract: Graph Transformers excel in long-range dependency modeling, but generally require quadratic memory complexity in the number of nodes in an input graph, and hence have trouble scaling to large graphs. Sparse attention variants such as Exphormer can help, but may require high-degree augmentations to the input graph for good performance, and do not attempt to sparsify an already-dense input graph. As the learned attention mechanisms tend to use few of these edges, however, such high-degree connections may be unnecessary. We show (empirically and with theoretical backing) that attention scores on graphs are usually quite consistent across network widths, and use this observation to propose a two-stage procedure, which we call Spexphormer: first, train a narrow network on the full augmented graph. Next, use only the active connections to train a wider network on a much sparser graph. We establish theoretical conditions when a narrow network's attention scores can match those of a wide network, and show that Spexphormer achieves good performance with drastically reduced memory requirements on various graph datasets.

Even Sparser Graph Transformers
Hamed Shirzad
Honghao Lin
Balaji Venkatachalam
University of British Columbia shirzad@cs wbc.
Carnegie Mellon University honghaol Candrew..nrww.... cmu.edu
Meta
baveêmeta.com com
Ameya Velingker
David P. Woodruff CMU & Google Research dwoodruf @cs. cmu. edu
Danica J. Sutherland
Independent Researcher" ameyav@gma1l.com
UBC & Amii dsuthēcs .uc.c.s..bcc.
Abstract
Graph Transformers excel in long-range dependency modeling, but generally require quadratic memory complexity in the number of nodes in an input graph, and hence have trouble scaling large graphs. Sparse attention variants such Exphormer can help, but may require high-degree augmentations to the input graph for good performance, and do not attempt to sparsify already-dense input graph. As the learned attention mechanisms tend to use few of these edges, such high- degree connections may be unnecessary. We show (empirically and with theoretical backing) that attention scores on graphs are usually quite consistent across network widths, and use this observation propose two-stage procedure, which call Spexphormer: first, train a narrow network on the full augmented graph. Next, use only the active connections to train wider network much sparser graph. We establish theoretical conditions when a narrow network's attention scores can match those of wide network, and show that Spexphormer achieves good performance with drastically reduced memory requirements on various graph datasets. Code can github...h..... http://aamee111///S_Ep_pppp be found hhttps://// /tttps://githbb
Introduction
The predominant story of the last half-decade of machine learning has been the runaway success of Transformer models (Vaswani et al.) 2017), across domains from natural language processing
(Vaswani et al.) 2017 Devlin al. 2018 Zaheer et al.) (2020) to computer vision (Dosovitskiy et
2020) and, more recently. geometric deep learning (Dwivedi and Bresson 2020 Kreuzer et al. 2021 I
Ying et al., 2021 Rampášek et al. 2022: Shirzad al. 2023 Müller et al. 2023). Conventional ("full") Transtorrrs,,,,,r,, however, have a time and memory complexity of Ondd + +ndd). where n is the number entities (nodes, in the case of graphs), and d the width of the network. Many attempts have been made to make Transformers more efficient (see Tay al. (2020) for survey efficient transformers for sequence modeling). One major line of work involves sparsifying the attention mechanism, constraining attention from all (n² pairs to
smaller of connections. For instance, for sequential data, BigBird (Zaheer et al. 2020) constructs a sparse attention mechanism by combining sliding windows, Erdos-Rényi auxiliary graphs, and universal connectors. On the other hand, for graph data, Exphormer (Shirzad et al.) 2023) constructs sparse interaction graph consisting of edges from the input graph, overlay expander graph, and universal connections. We refer to such a network as a sparse atlention network.
Exphormer reduces each layer's 's complexity from Onnd ndd to O( + n)d?), where is the number nodes, m the number interaction edges in the sparse attention mechanism, and is
Work done in part while Google.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the hidden dimension or width. Even so, training is still very -emooy-intenssvve for medium to large scale graphs. Also, for densely input graphs with ((n2) edges, there is no asymptotic improvement in complexity, as Exphormer uses all of the O(n²) edges of the original input graph. Our goal is to scale efficient graph Transformers, such as Exphormer, to even larger graphs.
One general approach for scaling models to larger graphs is based on batching techniques. Prominent approaches include egocentric subgraphs and random node subsets (Wu et al., 2022 2023 2024).
Egocentric subgraphs choose a node and include all of its k-hop neighbors; the expander graphs used in Exphormer, however, are exactly defined so that the size of these subgraphs grows exponentially in the number of layers prohibitively expensive for larger graphs. A similar issue arises with nodes, whose representation depends on all other nodes. For uniformly- random subset batching. as the number b of batches into which the graph is divided grows, each edge has chance & to appear in a given step. Thus, b cannot be very large without dropping important edges. A similar problem can happen in random neighbor sampling methods such as GraphS (Hamilton) jet al. 2017). Although this model works well on message-pant paagge--psnngggg neural networks (MPNNs) which only use the graph edges, using it for expander-augmented graphs will select only small ratio of the expander edges, thereby breaking the universality properties provided by the expander graph.
nniversally-conneeee
Expander graphs enable global information propagation, and when created with Hamiltonian cycles and self-lopps, produce a model that can provably approximate full Transformer (Shirzad et al.) 2023 Theorem E.3). Yet not all of these edges turn out to be important in practice: we expect some neighboring nodes in the updated graph to have more of an effect on given node than others. Thus, removing low-impact neighbors can improve the scalability of the model. The challenge is to identify low-impact edges without needing to train the (too-expensive) full model. Figure T illlstrrates advantages of this batching approach other; this is also discussed further in Appendix E
One approach is to train smaller network identify which edges are significant. is not obvious priori that attention scores learned from the smaller network will estimate those in the larger network, but we present an experimental study verifying that attention scores are surprisingly consistent as the network size reduces. We also give theoretical indications that narrow networks are capable of expressing the same attention scores as wider networks of the same architecture.
Our approach. We first train a small-width network in order to estimate pairwise attention score patterns, which we then use to sparsify the graph and train a larger network. We first train the graphs without edge attributes. This reduces the complexity of Exphormer to O(md + nd?) and then by training much smaller width d₂ < d network, reduces the time and memory complexity by at least a factor of d/d,, We also introduce two additions to the model to improve this consistency. Training this initial network can still be memory-intensive but the small width implies the matrix multiplications are small, it is practical to train this initial model on a CPU nodes with sufficient RAM (typically orders of magnitude larger than available GPU memory), without needing to use distributed computation. Once this initial model is trained, the attention scores can be used in creating a sparse graph, over which we train the second network. These initial attention scores can be used as edge features for the second network.
As mentioned previously, to sparsify the graph. By selecting a fixed number e of edges per attention layer for each node, we reduce the complexity of each layer to O(nd² + rdc).. This sparsification alleviates the effect of a large number of edges, and allows for initial training with a larger degree expander graph, since most of the expander edges will be filtered for the final network. This sparsification differs from conventional graph sparsification algorithms (for MPNNs) in three ways. First, we use expander edges, self-loops, and graph edges and sparsify the combination of these patterns together. Second, this sparsification is wiiee which means that in a multi-layer network the attention pattern will vary from layer to layer. Finally, our sampling uses a smaller network trained on the same task, identifying important neighbors based on the task, instead of approaches independent of the task such as sampling based on RageRank or a neighbor's 's node degree.
use the attention scores obtained from the trained low-width network
Another advantage of this approach is that the fixed number of neighbors for each node enables regular matrix calculations instead of the edge-wise calculations used by Kreuzer et al.) (2021): Shirzad et al. (2023), greatly improving the speed of the model. After this reduction, batching can be done based on the edges over different layers, enabling Transformers to be effectively batched while still effectively approximating the main Transformer model, enabling modeling long-range -aage dependencies. In batching large graphs, sampling without replacement from attention edges with varying weights can be very
2

---

(a)
(b)
(c)
(d)
(e)
Figure 1: Figure (a) shows very simple synthetic graph where each node has binary classification task of determining whether there exists a node the opposite color in the same connected component. This task requires learning long-range raang dependencies. Figure (b) shows a natural clustering of the graph. This clustering would mean no node can do its task if models are trained only on the clusters. Figure (c) shows neighbor sampling starting from the green node, where random sampling fails to select the important edge that bridges the two different colored nodes. Figure (d) shows random subset sampling strategy that the task is solvahle if and only the two sides of the hridge between the two colors get selected, Now we keep increasing the size of both sides of the bridge, while keeping just one edge between two colors, the probability of selecting the bridge in any batch goes to zero, and thus the training will fail in this scenario. (e) shows attention scores between the nodes if trained with an attention-based network. Dashed lines have zero attention scores, and thicker lines indicate a larger attention score. Knowing these attention scores will mean each node with just one directional edge can do the task perfectly. The attention edges are shown (f). In case two nodes are cqually informative selecting either of them leads to the correct result.
slow. This especially true if the attention scores are highly concentrated on a small number of neighbors for most of the nodes. Sequential sampling of neighbors can be very slow, while parallel sampling can lead to many conflicts in this scenario. We use reservoir sampling, enabling parallel sampling with an easy, efficient GPU implementation, improving the sampling process significantly.
We only use the Transformer part of the Exphormer model, not the dual Tranffrraeformer architecture used by [Shirzad et al. (2023); Rampášek et al. (2022). Unlike the Exphormer approach, we do not assume that the expander graph is of degree O(I); we can see this as interpolating between MPNNs and full Transformers, where smaller degree expander graphs mostly rely on the graph edges and are more similar to MPNNs, while higher degree expander graphs can resemble full attention, in the most extreme case of degree 1 exactly recovering a full Transformer.
To summarize, the contributions of this paper are follows: I.) We experimentally and theoretically analyze the similarity of attention scores for networks of different widths, and propose two small architectural changes to improve this similarity. 2.) We propose layer-wise sparsification, by sampling according to the learned attention scores, and do theoretical analysis on the sparsification guarantees of the attention pattern. 3.) Our two-phase training process allows us scale Transformers to larger datasets as it has significantly smaller memory consumption, while maintaining competitive accuracy.
2 Related Work
Graph Transformer Architectures. Attention mechanisms were proposed in early (message- passing) Graph Neural Network (GNN) architectures such as Graph Attention Networks (GAT) (Velčković al. 2018), where they guide node aggregation among neighbors, without using positional encodings. GraphBert (Zhang et al., 2020) finds node encodings based on the underlying graph structure. Subsequent work has proposed full-fledged graph Transformer models that generalize sequence Transformers (Dwivedi and Bresson 2020) and are not limited to message passing between nodes of the input graph; these include Spectral Attention Networks (SAN) (Kreuzer et al. 2021), Graphormer (Ying et al. 2021), GraphiT (Mialon et al.) 2021). etc. GraphGPS (Ram- pášek et al. 2022) combines attention mechanisms with message passing, allowing the best of both worlds.
3

---

Efficient Graph Transformers. Several recent works have proposed various scalable graph trans- former architectures. NAGphormer (Chen et 2022a) and Gophormer (Zhao et al., 202I) use sampling-based approach. On the other hand, Difformer (Wu et al. 2023) proposes a continuous time diffusion-base basiio transformer model. Exphormer (Shirzad et al. ) proposes a sparse graph that combines the input graph with edges of an expander graph as well as virtual nodes. They show that their model works better than applying other sparse Transformer methods developed for sequences. Another work, NodeFormer (Wu et al. 2022), which is inspired by Performer (Choromanski et al. 202Ip, uses the
operator as a kernel to efficiently propagate information among all pairs of nodes. SGFormer (Wu et al., 2024) shows that just using one layer transformer network can sometimes improve the results of GCN-based networks and the low memory footprint can help scale to large networks. Perhaps most conceptually similar to our work is Skeinformer (Chen et al.) 2022b), which uses sketching techniques to accelerate self-attention.
Sampling and batching techniques. Some sampling-hased based methods have been used to alleviate the problem of "neighborhood explosion." " For instance, sampling was used in GraphSAGE (Hamilton ct al. 2017). which used fixed-size sample from neighborhood in the node aggregation step. GraphSAINT (Zeng et al., 2020) scales GCNs to large graphs by sampling the training graph to create minibatches.
Other. Expander graphs were used in convolutional networks by Prabhu et al. 2018
3 Preliminaries and Notation
Exphormer. EXPHOORMER is expander-based sparse attention mechanism for graph transformers that uses O[IVI+ [E]) computation, where G = (V, E) is the underlying input graph. Exphormer creates an interaction graph H that consists of three main components: edges from the input graph, an overlaid expander graph, and virtual nodes (which are connected to all the original nodes).
For the expander graph component, Exphormer uses a constant-degree random expander graph, with O(n) edges. Expander graphs have several useful theoretical properties related to spectral approximation and random walk mixing, which allow the propagation of information between pairs of nodes that are distant in the input graph G without explicitly connecting all pairs of nodes. The expander edges introduce many alternative short paths between the nodes and avoid the information bottleneck that can be caused by the virtual nodes.
Our model. We use H to denote the attention pattern, and (i) the neighbors of node i under that pattern. Let X = (x1, .2....,,,,) E _dxn be the matrix of d-dimensional embeddings for all of the nodes. Our primary "driver" is then h-head attention: using @ for element-wise multiplication,
ATTN (X) X;
Σ V a j=1
K. of +B')
where V/- W(.XN.O). K= W XN and Q W are linear mappings of the node features for the neighbors XN (i), and E W WgEN and B = W (1) are linear maps of the edge features ε, which is a dg x (i) matrix of features for the edges coming in to node i. Exphormer uses learnable edge features for each type of added edge, and original edge features for the graph's 's edges. If the graph does not have any original edge features, it uses learnable edge feature across all graph edges. Edge features help the model distinguish the type of attention edges, Here, a is an activation function. In both Exphormer and our work the activation function is ReLU.
In the absence of edge features, which is the case for most of the transductive datasets, including the datasets that have been used in this paper, &, for any attention edge e can have one of three possible representations, and E/ can be computed more simply by first mapping these three types of edge features with W for head j, and then replacing the mapped values for each edge type. This simple change reduces the complexity of the Exphormer from Ommd + nd?) to O(md + nd?).
Compared to prior work, we introduce B' as a simpler route for the model to adjust the importance of different edge types. Considering Exphormer as an interpolation between MPNNs and full Transformers, the B' model has an easier path to allow for attention scores to be close to zero for all non-graph attention edges, without restricting the performance of the attention mechanism

---

graph edges, Consequently, it can function roughly as an MPNN (similar to GAT) by zeroing out the non-local attention paths. We use dæ d, and have each layer output features of the same width as its input, so that each of the W parameter matrices except for B are d x d, and W is
As simple illustration that E' is insufficient to allow near zero attention scores, thus highlighting the importance of B', note that if the columns of K and Q are distributed independently and uniformly on unit ball (e-g., under random initialization). there is no vector E/ which is identical for all edges of an expander graph that can make the attention scores for all the expander edges near-zero.
Our network compared to Exphormer. We use Exphormer the base model because it provides us the flexibility to adjust the sparsity of the attention graph and to interpolate between MPNNs and full Transformers. Exphormer can model many long-range dependencies that are not modeled by MPNNs and are very expensive to model in a full Transformer. For example, one cannot train a full Transformer model in the memory of conventional GPU device for dataset such Physics, which has a graph on just 34K nodes. In our instantiation of Exphormer, we add self-loops for every node and use d/2 random Hamiltonian cycles construct our expander graph as described in (Shirzad) et al. 2023 Appendix C.2). We do not add virtual nodes in our networks (note that the resulting network is still a universal approximator; (Shirzad al.) 2023 Theorem E.3). Although the best known results for Exphormer combine sparse attention with MPNNs, in this work, we avoid the MPNN component for scalability reasons. We also make two additional changes, see Section 4
Method
Our method consists of two-phase training process. The first phase trains a model we call the Attention Score Estimator Network, whose goal is to estimate the attention scores for a larger network. This model is not particularly accurate; its only goal is for each node learn which neighbors are most important. The learned attention scores for each layer of the first network are then used to construct sparse interaction graphs for each layer in a second model, which is trained (with hyperparameter tuning for the best results) and serves as the final predictor.
Attention Score Estimator Network. For this network, use width of 4 8, with just one attention head, in our training. We tune the other hyperparameters in order to have a converged training process with reasonably high accuracy, but we do not spend much time optimizing this network as it is sufficient to learn the important neighbors for each node, i.e., edges with high attention scores. This network will be trained with many layers as the final network we want to train. Because it is so narrow, it has many fewer parameters and hence much less memory and time complexity, making it cheaper to train. Moreover, we only need to do this training once per number of layers we consider, conditioned on the fact that the training converges, even if the final model has large number of hyperparameters. Compared Exphormer, we use much higher-degree expander graph: 30 to 200 instead of the 6 used for most transductive graphs by (Shirzad et al. (202)). As most of the considered datasets do not have edge features, we use a learnable embedding for each type of edge (graph edge, expander edge, or self-loop). We also make two small changes to the architecture and the training process of this model, discussed below. Section 5 shows experimentally that the low-width network is good estimator of the attention scores for a Targe-width network.
Normalizing V. Having smaller attention score, aij aaj', does not necessarily mean that j's contribution to i's new features is smaller than that of j if |V >>>>> V the net contribution of j could be larger. Although Transformers typically so after mapping X to V. We normalize the rows of V to have the same vector sizes for all nodes. In our experiments, normalizing to size one reduced performance significantly; however, adding learnable global scale s, so that V, becomes .V; maintained performance while making attention scores more meaningful.
layer normalization, they do not typically do
||Villa
Variable Temperature One of the side goals is to have sharper attention scores, guiding the nodes to get their information from as few nodes as possible. Using temperature in the attention mechanism can do this, where logits will be divided by temperature factor 7 before being fed into a softmax. Normal attention corresponds to T = 1; smaller means sharper attention scores. However, setting the temperature to small value from the beginning will make the random initialization more significant, and increase the randomness in the training process. Instead, we start with v = 1.0 and gradually anneal it to 0.05 by the end of the training. We set initial phase for X epochs
5

---

Network
Low-witth
Feed Netwock
1e Me
Laysr
Spine
Ade SoftMe
Samelize
Die Produce
(a)
(b)
(c)
High-witth
Feal Notwrrk
Newwork
Layer
Spanse MalMul
Layer-wise Sampling 1
Addl SulMMaa
Dut Product
(d)
(e)
Figure 2: Steps of our method. (a) The attention mechanism for the attention score estimator network combines graph edges with expander graph and self-loops. The expander graphs are constructed hy combining small number of Hamiltonian cycles here two, in red and in purple then confirming the spectral gap is large enough. (b) Self-attention layers in the estimator network use this sparse attention mechanism; its self-attention layers normalize V. (c, d) Attention scores are extracted from this network for each layer, and used to sample, in (e), a sparse directed graph, which becomes the attention graph for the final network (f). This network, with much larger feature dimension, does not normalize V.
where we use T = 1; this lets the model learn which neighbors are more important for each node slowly. We multiply with factor y after each epoch, obtaining temperature in epoch t > X of max(y f- 0.05). We use À = 5 and 7 = 0.99 or 0.95 depending on how fast the learning converges.
Sparser Attention Pattern. The memory and time complexity of Exphormer is linearly dependent on the number of edges. Also, with a small number of layers, the expander degree should be high enough ensure large enough receptive field for each node in order to learn the long-range dependencies. Not all these edges are equally important, and many of them will have a near-zero effect on the final embedding of each node. Reducing the number of edges can alleviate memory consumption. Additionally, a sparser pattern lets us use batching techniques for the larger graphs. In this work, we analyze how effectively the sparser model can work and up what factor we can sparsify. For each layer, e.g.. L, we select a deg, as fixed degree for each node and sample without replacement according the attention score estimator network's 's attention scores in each epoch of training or evaluation. Having the same degree for each node's 's attention pattern also means that attention can be calculated using (much-more-optimizee
standard matrix multiplications, rather than the propagation techniques used in Exphormer and SAN (Kreuzer et al. 2021).
To sparsify the graph, in each epoch, sample new set of edges according the learned attention scores from the smaller network. The reason why we do this rather than simpler strategy such as selecting top-scored edges that in many cases, several nodes can have very similar node features. If we assume nodes u1, U2,..., Up from the neighbors of node v have almost the same features, and the attention scores for these nodes are Qr,, .'2...., ap.. any linear combination of Σ a; = a will lead to the same representation for node v. If features are exactly the same, a will be divided between these nodes, and even if a is large, each node's attention score from v can be small. By sampling, we have total chance of selecting any of the nodes U1pp. In each epoch, we re-sample new set of edges for each node from its original neighborhood.
Faster Sampling Using Reservoir Sampling. Sampling without replacement using default li- brary calls is very slow, especially if few neighbors dominate the attention scores. We instead use reservoir sampling (Efraimidis and Spirakis| 2006), which is GPU-friendly and parallelizable. For reservoir sampling of k neighbors from the neighborhood of node i, with attention scores (41, az ... (()), we first do uniform random sampling of u = (u1. u2, "[Nin ())) where the i, are i.i.d. samples from Uniform(O. 1). Then calculate log (u) with clement-wist

---

multiplication, and select the indices with the top l values from this list. Selecting k-th rank from values and pivoting has worst-case (n) time algorithm. which much faster than the (nk) worst case time for trial-and-error. Pseudocode is given in Algorithm]] [ The GPU-friendly version of this can be implemented by sampling for nodes in parallel, but requires forming a regular matrix for the attention scores, which can be done by extending each attention score vector by the maximum degree, or selecting a value k' > k and first sampling k' and selecting the top attention scores from each node, making sure that the sum of the rest of the neighbor's 's attention scores are very near to zero. Then by forming a rectangular attention matrix, uniform sampling and element-wise multiplications much faster GPU, and sampling from the entire batch is much more efficient.
Algorithm Reservoir Sampling from a Node's 's Neighborhood
Input: Attention scores a = (0 in (s) number of neighbors to sample: deg,
Output: List of deg, neighbors of node i
1: function RESERVOIRS deg,)
2: u Uniform(O, 1) Warcl
3: return argtopdeg, ( log(u))
4: end function
Batching. Each batch starts with a random subset of "target" nodes B. These are the nodes whose last-layer representations we will update in this optimization step. To calculate these representations, we need keys and values based on the previous layer's representations for the relevant neighbors of each target node (again, sampling neighbors from the graph augmented by an expander graph). To approximate this, we sample degı neighbors for each target node. Then we have a set of at most [degg, +1) nodes whose representations we need calculate in layer L- repeat this process, so that in layer we need to compute representations for up to @( < min( II -11 (deg, +1), n)
query nodes, with [Q() deg, attention edges. Pseudocode is given in Algorithm
When the number of layers L and degree deg, are not too large, this batching can be substantially more efficient than processing the entire graph. Moreover, compared to other batching techniques, our approach selects neighbors according to their task importance. Except for optimization dynamies in the training process corresponding to minibatch versus full-batch training, training with batches identical to training with the entire sparsified graph; if we choose large deg, equal to the maximum degree of the augmented graph, this is exactly equivalent to SGD on the full graph, without introducing any biases in the training procedure. This is in stark contrast to previous approaches, as illustrated in Figure 1 Unlike these prior approaches, which typically use the full graph inference time, we can run inference with batch size as small as one (trading off memory for computation).
Algorithm 2 Neighborhood Sampling for Batch of Nodes
se number of neighbors to sample in each layer: deg = (deg), ... degr.). and a batch nodes V Output: Q(0), x((), V(O,, query, key, and value nodes in each layer
Input: Attention scores in each layer: a = a Vi E +EE
1: function SAMPLLENICCHHOOOOOOO deg)
2: ((++1) +- B
3: for Lo do
4: Q(1) + vie+1)
5: for i tii Q do
6:
+ R
7:
end for
8: (C + Useor x
9: DO Qlt) Uk(o
end for
11: return {((9)
[1
12: end function
7

---

Fixed Node Degree Layers. Sparse matrix operations are not yet nearly as efficient as dense operations on GPU devices. Exphormer and SAN use gather operation, which is memory-efieiint but not time-efficient on GPU (Zaheer et al. 2020). By normalizing the degree, instead of having |0(0) deg, separate dot products between the query and key vectors, we can reshape the key vectors to be of size [ x deg xd and the query is of shape [Q(0] x d. Now the dot product of query and key mappings can be done using ( deg xd by d x matrix multiplications. This same size matrix multiplication can be done using highly optimized batch matrix multiplication operations in
e.g. PyTorch and Tensorflow (Paszke et al. 2019 Abadi et al. 2015).
Theoretical Underpinnings. We first study the approximability of network with smaller hidden dimension or width. Formally, suppose that the width of a wide network is D. Then there exists a network with narrow dimensions for Wo and WK, K, of dimension Of log 12 x D instead of D x D, whose attention scores agree with those of the wide network up ((e) error (Theorem D.4). This reduction helps with the most intensive part of the calculation; others are linear with respect to the number of nodes n. While this is not the model we use in practice, [Shirzad et al. (2024) Section 4) explore some scenarios common in graph Transformers that allow for the existence of "fully" narrow networks with accurate attention scores. They support these claims with experiments that show compressibility for some datasets we use. This is an existence claim; we will justify experimentally that in practice, training a narrow network does approximate attention scores well.
We then study the sampling procedure of our sparsification method. Under certain assumptions, show that sampling roughly O(n log n//²) entries of the attention matrix A (corresponding to sampling this many edges in the graph) suffices to form a matrix B with || BII2 S E| All. can access the entries of A (Theorem D.5). We cannot actually access the matrix A, but do have attention scores A' from a narrow network. We show that if the entries of A are not seriously under-estimated by A', the same bound the number of samples still holds (Proposition D.7p.
5 Experimental Results
Actor Dataset without Expanders
Dataset Exponders
Photo Datoset without Expanders
Photo Daleset with Expanders
0.50
0.20
0.3
0.08
0.06
0.15
0.10
0.2
04
0.05
0.02
0.0
0.00
untor
nandon
0.00
undcom
mendom
0.00
unitomm
rendem
undonn
mindon
(d)
Figure 3: Energy distance between the attention scores of various networks network of width 64. "Uniform" refers to the baseline placing uniform scores on each neighbor, while "random" refers to the baseline with uniformly distributed logits. The remaining bars refer to networks trained on the appropriately labeled width.
Attention Score Estimation. To show how well the smaller network estimates the attention scores for a larger network, we conduct experiments on two smaller datasets, where we can reasonably train the full network at higher width for many runs to be able to have estimation on the distribution of the attention scores. To this end, we use Actor (Lim et al. 202T) and Photo (Shchur et al. 2018) datasets. We train the network for hidden dimensions, h varying from 4 to 64 for both datasets. For each h we train the network 100 times. We consider the distribution of attention scores for each node and estimate the energy distance (Székely and Rizzo 2013]_ an instance of the maximum mean discrepancy, [Sejdinovic et al. 2013) for that node across each pair of h sizes.
We ran this experiment both when learning with just graph edges, and when adding expander and self-loop edges. It might be that the model, just by examining the category of the edges, may give lower score to type, making distributions seem more similar despite not identifying small number of important neighbors as we want. However, in the presence of only one type of edge, the model can still consistently estimate which nodes should have a higher attention score.
We compare attention scores from our model with the uniform distribution on the neighbors (each neighbor of node has score + and to distribution with logits uniform over [-8,8] The choice of
8

---

8 here is because in the network we clip the logits with an absolute value higher than 8. FigureBishowe shows that even width-4 networks provide far superior estimates of attention scores than these baselines.
Table 1: Comparison of our model with other GNNs on five homophilic and three heterophilic datasets. The reported metric is ROC-AUC (x 100) for the Minesweeper and Tolokers datasets and accuracy for all others. The average edge ratio is the degree of the nodes in Spexphormer over the average degree of the nodes in the initial attention pattem.
Model
Cumputer
Ploto
CS
Physic
ugbo-arsin
Model
Actur
Minesroper
Telskers
GCN
59.65 0.52
92:70
0.20
92.92 1: 0.12
16.18 =: 0.07
71.74 = 0.29
GLOGNN
36,6 2:
51.05 1: 1.23
73.39 2: 1.17
GRARSSAGE
91.20 0.24
91.59
0.14
03.91
2:0.3
$6.49 2: 036
71.49 2:127
GCN
3522521.16
59.75 1.052
83.64 2: IL67
96.17
72.01 =:030
GRAPIGPS
GRAPESAINT
00.22
63.50
NAGHIORMER
78.32
91.19
7000
72.41
EXPRORAEE--CC
0.15
97.16
72.44 0.25
0.338
1:0.5
83.77
EXPHIORAFRR
91.16
0.76
0.17
95.19
0.26
$6.40 0:30
71.37
0:0.2
EXPHORAFER
19.11
92.25 0.56
83.53
SPENPIORMER
/M 0:08
95.31 0.49
95,00
0:15
20
70.2
SPERPHORMIER
38.59 0:31
90.21 0.1.7
85 54
Edge Perazia
7.6%
8.28
12.8%
11.3%
13.7%
Elge Penezni
5.8%
17.8%
3.9%
Seacpherrar
Model
ngba-preoteins
Amazon2M
Pokec
Daphomerr Begnna
Exgiurner Degiee 20
60.15
GCN
72.51 +: 0.35
83.90
0.30
62.31
1.13
SGC
70.31 4: 0.23
81.21
4: 0.12
52.03
0.84
Megabtes
GAT-NSAMPLER
ACM-ER
73.51
1: 1.31
83.84
1: 0.42
62.32-1.088
63.75
0.77
SIGN
71.24 1: 0.46
80.98
0.31
68.01
0.25
NODEFORMER
77.45 4 1.15
87.85
1: 0.24
70.32
0:45
15000
SGFORMER
79.53 :: 0.38
89.09
0.10
73.76
0.24
SPEXPHORMER
19300
Memory Information for SPEXPIOORMI
Menory (MB)
2232
3262
2128
Butch
1000
5000
Hidden Dimension
64
Number of layen
2
2
2
Number of Parameters
79,224
300,200
83,781
Figure 4: Memory usage comparison: Attention Score Estimator network and Spexphormer vs. Exphormer with expander degrees 6 and 30. Exphormer with de- gree 30 for the ogbn-arxiv dataset could not fit into the memory of a 40GB GPU device, and thus the number is a lower bound here.
Table 2: Comparative results on large graph datasets, with ROC-AUC(X 100) reported for the ogbn-proteing dataset and accuracy for all others. GPU memory usage, batch sizes, hidden dimensions used obtaín these numbers, and total number of parameters have been added at the bottom of the table.
Model Quality. We conduct experiments on eight medium- sized graphs, including five homophilic datasets: CS, Physics, Photo, Computer (Shchur et al., 2018)) and ogbn-arxiv (Hu al. 2021] 1); and three heterophilic datasets: Minesweeper, Tolokers (Platonov et al., (203),, and Actor (Lim et al.) 202T). For the CS, Physics, Photo, and Computer datasets, we use random train/validation/eestt split of 60%%20%%/20%. For ogbn-arxiv we follow the standard data split provided by the original source. For the Actor dataset, we use a 50% split following Wu et al. (2022). For the Minesweeper and Tolokers datasets, we use the standard split from Platonov et al. (023). Results for these experiments are provided in Table [
In these medium-sized datasets, we are able to train the full Exphormer model. Our goal is to determine the extent of performance reduction when using two memory-effictt networks to estimate the original network. Results show that the two aeemory-effiiiem networks can efficiently estimate the original network, enabling us to scale the ExphoRMER to larger graph datasets. We compare the maximum required memory of the attention score estimator and final networks with that of the corresponding EXPHIORMER model in Figure
We then experiment on large graph datasets (ogbn-proteins, Amazon2M (Hu et al., 2021) and Pokec (Takac and Zabovsky 2012)). ). The results provided in Table demonstrate superior performance of our model despite limited memory constraints. We follow the standard data split for the ogbn-proteing dataset and follow Wu al. (2024) for the dataset split on the Amazon2M and Pokec datasets, with 10% 10%/10%/888 10%/80% and 50%/25 50%/255//254 %725% train/validation/tesd ratios. We emphasize that this split differs from the original dataset split used by many other works, making those numbers incomparable.
In all our experiments, we train the smaller network once, and then for the second network, we always use the same initial network's learned attention scores. Attention scores are collected from the network training step with the highest validation accuracy.

---

Table 3: Ablation studies on homophilic and two heterophilic datasets. Metries: accuracy for Photo and Computer, ROC-AUC (x100) for Tolokers and Minesweeper. For initial network, we report the result the network used for training the Spexphormer and thus, there is no confidence interval for them.
Model/Dataset
Computer
Photo
Minesweeper
Tolokers
Initial Network
85.23
91.70
85.67
80.16
Spexphormer uniform
86.65 0.46
0.22
84.15
0.17
Spexphormer-max
89.31 + 0.31
95.07
0.20
87.92 + 0.26
80.85 + 0.23
Spexphormer w.o. temp
89.05 + 0.35
95.30 0.16
90.02 - 0.02
83.34 0.13
Spexphormer layer
89.70 = 0.25
94,91
1: 0.18
89.65 4 0.10
84.06
0.10
Spexphormer
91.09 = 0.08
95.33 = 0,49
90.71 # 0.17
83.34 = 0.13
We use a subset of the following models in each of our tables as baselines, depending on the type of the dataset and scalability level of the models, GCN (Kipf and Welling 2016), GraphSAGE (Hamilton
et al. 2017), GAT (Veličković et al., 2018), GraphSAINT (Zeng et al. 2020). Nodeformer (Wu et al.
2022). Difformer (Wu al. 2023). SGFormer (u al. 2024), GraphGPS (Rampášek et al.) [002]] I
GOAT (Kong et al.) 2023). GloGNN (Li et al. 2022). SGC (Wu et al. (2019), NAGphormer (Chen
al. 2022a), Exphormer (Shirzad et al. (2023). ) SIGN (Frasca et al. (2020)) We borrow most of the
baseline numbers in the tables from Wu et al. (2024); Deng et al. (2024).
Ablation Studies. We benchmark the effect of different parts of the model in Table 3 Spexphormer- uniform, rather than sampling based on the estimated attention scores, samples uniformly from the augmented graph: this is always worse than sampling, but the gap is larger for some datasets than others. Spexphormer-max takes the edges with the highest attention scores, rather than sampling; this again performs somewhat worse across datasets. Spexphormer w.o. temp uses constant temperature of I in the initial attention score estimator network; Spexphormer w.o. layer norm removes our added layer normalization. these changes are smaller, and in one case layer normalization makes the results worse. Across the four datasets, however, it seems that both temperature and layer norm help yield more informative and sparser attention scores.
Conclusion & Limitations
We analyzed the alignment of the attention scores among models trained with different widths. We found that usually the smaller network's 's attention score distributions align with the larger network's s. We also theoretically analyzed the compressibility of the larger Graph Transformer models. Based on these observations, smaller number of edges per layer. As a result of these two steps, the model's memory consumption reduces significantly, while achieving competitive accuracy. This strategy also lets batching techniques that were not feasible with expander graphs of a large degree. Having a regular degree enables using dense matrix multiplication, which is far more efficient with current GPU and TPU devices.
used sampling algorithm to sparsify the graph each layer and sampled
novel
While our method successfully scales to datasets with over two million nodes, it relies large CPU memory for the attention score estimation for these datasets. For extremely large datasets, this is still infeasible without highly distributed computation. Estimated attention scores used for training various networks based on attention scores, however, so this only needs to only be computed once per dataset and depth. An area for potential future work is to combine sampling with simultaneous attention score estimation in a dynamic way, scaling this estimation to very large graphs.
be shared and
Acknowledgments and Disclosure of F Funding
This work was supported in part by the Natural Sciences and Engineering Resource Council of Canada, the Fonds de Recherche du Québec Nature et technologies (under grant ALLRP-57708- 2022), the Canada CIFAR AI Chairs program, the BC DRI Group, Calcul Québec, Compute Ontario, and the Digital Resource Alliance of Canada. Honghao Lin was supported in part by a Simons Investigator Award, NSF CCF-2335412, and CMU Paul and James Wang Sercomm Presidential Graduate Fellowship.
10

---

References
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving. G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg. J., Mané, D., Monga, R., Moore, S., Murray, D.. Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng. X. (2015). TensorFlow: Large-scale machine learning on heterogeneous systems. Software available from tensorflow.org.
Achlioptas, D., Karnin, Z. S., and Liberty. E. (2013). Near-optimal entrywise sampling for data matrices. Advances in Neural Information Processing Systems, 26.
Chen, J., Gao, K., Li, G., and Hc, K. (2022a). Nagphormer: Neighborhood aggregation graph transformer for node classification in large graphs. CoRR, abs/2206.0499
Chen, Y., Zeng, Q., Hakkani-Tur, D., Jin, D., Ji, H., and Yang, Y. (2022b). Sketching tool for understanding and accelerating self-attention for long sequences. In Carpuat, M., de Marneffe, M., and Ruíz, I. V. M., editors, Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022, pages 5187-5199, Association for Computational Linguisties.
Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlós, T., Hawkins, P., Davis, J. Q.. Mohiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. (2021). Rethinking attention with performers. In ICLR.
Deng, C., Yue, Z.,, and Zhang. Z. (2024). Polynormer: Polynomial-expressivee graph transformer in linear time. arXiv preprint arxiv:2403..1222.
Devlin, J., Chang. M.-W., Lee, K., and Toutanova, K. (2018). Bert:
Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 18Xiv:1810. 1810.088.
Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. (2023a). On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pages 7865-7885. PMLR.
Di Giovanni, F., Rusch, T. K., Bronstein, M. M., Deac, A., Lackenby, M., Mishra, S., and Veličković, P. (2023b). How does over-squashing affect the power of gnns? arXiv preprint arXiv:2306. 03589.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. (2020). An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010.1 1929..
Dwivedi, V. P. and Bresson, X. (2020). A generalization of transformer networks to graphs. CoRR, abs/2012.09669..
Efraimidis, P. S. and Spirakis, P. G. (2006). Weighted random sampling with reservoir. Information processing letters, 1815188
Franks, B. J., Morris, C., Velingker, A., and Geerts, F. (2024). Weisfeiler-leman at the margin: When more expressivity matters. arXiv preprint X7X1:2440..05568
Frasca, F., Rossi, E., Eynard, D., Chamberlain, B., Bronstein, M., and Monti, F. (2020). Sign: Scalable inception graph neural networks. arXiv preprini urXiv:2004.1 1798.
Hamilton, W., Ying, Z., and Leskovec, J. (2017). Inductive representation learning large graphs. Advances in neural information processing systems, 30.
Hu, W., Fey, M., Ren, H., Nakata, M.. Dong, Y., and Leskovec, J. (2021). OGB-LSC: A large-scale challenge for machine learning on graphs. CoRR, abs/2103.09430.
Johnson, W. B. (1984). Extensions of lipshitz mapping into hilbert space. In Conference modern analysis and probability, 1984, pages 189-206.

---

Kakade. S. and Shakhnarovich, G. (2009). Lecture notes in large scale learning, https: //mmme
home
stic.edu// /ttp///rrrrrooooee//////adaaaaee
Kipt, T. N. and Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:
Kong, K., Chen, J., Kirchenbauer, J., Ni, R., Bruss, C. B., and Goldstein, T. (2023). Goat: A global
transformer on large-scale graphs. In International Conference on Machine Learning, pages 17375-17390. PMLR.
Kreuzer, D., Beaini, D., Hamilton, W. L., Létourneau, V., and Tossou, P. (2021), Rethinking graph transformers with spectral attention. arXiv preprint arXiv:2/06.03892
Li, X., Zhu, R., Cheng, Y., Shan, C., Luo, S., Li, D., and Qian, W. (2022). Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, pages 13242-1333 13256. PMLR.
Lim, D., Hohne, F., Li. X., Huang, S. L.,, Gupta, V., Bhalerao, O., and Lim, S. N. (2021). Large scale learning on non-homophae con-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 2-220887729005
Liu, X., Yan, M., Deng, L., Li, G., Ye, X., and Fan, D. (2021). Sampling methods for efficient training of graph convolutional networks: A survey. IEEE/CAA Journal of Automatica Sinica, 9(2):205-234.
Mialon, G., Chen, D., Selosse, M., and Mairal, J. (2021). Graphit: Encoding graph structure in transformers. CoRR, abs/2106.05667.
Müller, L.,, Galkin, M., Morris, C., and Rampášek, L. (2023). Attending to graph transformers. arXiv preprint 202.4:2302.04181.
Paszke, A., Gross, S.. Massa, F., Lerer, A., Bradbury, J.. Chanan, G., Killeen, T., Lin. Z., Gimelshein, N., Antiga, L., et al. (2019). Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32.
Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang. B. (2020). Geom-gen: Geometric graph convolutional networks, arXiv preprint arXiv:2002.05287
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. (2023). A critical look at the evaluation of GNNs under heterophily: Are we really making progress? arXiv preprint arXiv:2302.11641
Prabhu, A., Varma, G., and Namboodiri, A. M. (2018). Deep expander networks: Efficient deep networks from graph theory. In Ferrari, V., Hebert, M., Sminchisescu, C., and Weiss, Y., editors, Computer Vision ECCV 2018- 15th European Conference, Munich, Germany, September 8- 14, 2018, Proceedings, Part XIII, volume 11217 of Lecture Notes in Computer Science, pages 20-36. Springer.
Rampášek, I., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. (2022). Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:14501-1
Rusch, T. K., Bronstein, M. M., and Mishra, S. (2023). A survey oversmoothing in graph neural networks. arXiv preprint arXiv: 10993.
Sejdinovic, D.,, Sriperumbudur, B., Gretton, A., and Fukumizu, K. (2013). Equivalence of distance- based and RKHS- based statistics in hypothesis testing. The Annals of Statistics, 41(5):2263 2291.
Shehur, O., Mumme, M., Bojchevski, A., and Günnemann, S. (2018). Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.055
Shirzad, H., Lin, H., Venkatachalam, B., Velingker, A., Woodruff, D., and Sutherland, D. J. (2024). theory for compressibility of graph transformers for transductive learning. In Machine Learning and Compression Workshop at NeurIPS.
12

---

Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, J. and Sinop, A. K. (2023). Exphormer: Sparse transformers for graphs. ICML.
Székely, G. J. and Rizzo, M. L. (2013). Energy statistics: class of statistics based on distances. Journal of Stalistical Planning and Inference, 143(8):1249-127)
Takac, L. and Zabovsky, M. (2012). Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, volume 1.
Tay, Y., Dehghani, M., Bahri, D., and Metzler, D. (2020). Efficient transformers: survey. arXiv preprint arXiv:2009.0673
Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. (2021). Understand- ing over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.4522,,
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, (2017). Attention is you need. In NeurlPS, pages 5998-6008.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. (2018). Graph attention networks. In ICLR.
Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Weinherger, K. (2019). Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR.
Wu, Q. Yang, C.. Zhao, W., He, Y., Wipf, D., and Yan, (2023). Difformer: Scalable (graph) transformers induced by energy constrained diffusion. arXiv preprint arXiv:2301.09474.
Wu, Q. Zhao, W., Li, Z., Wipf, D. P., and Yan, J. (2022). Nodeformer: A scalable graph structure learning transformer for node classification. NewrIPS, 35:27387-27401.
Wu, Q., Zhao, W., Yang, C., Zhang, H., Nie, F., Jiang, H., Bian, Y., and Yan, (2024). Simplifying and empowering transformers for aarge-grahl representations. Advances in Neural Information Processing Systems, 36.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. (2021). Do transformers really perform bad for graph representation? ArXiv, 125/21000052244
Zaheer, M., Guruganesh, G., Dubey, A., Ainslie, J., Alberti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q. Yang, I.., et al. (2020). Big bird: Transformers for longer sequences. Advances in neural information processing systems, 33:17283-17299
Zeng. H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V. K. (2020). Graphsaint: Graph sampling based inductive learning method. In 8th International Conference Learning Represen- tations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net.
Zhang, J., Zhang, H., Xia, C., and Sun, L. (2020). Graph-Bert: Only attention is needed for learning graph representations. arXiv preprint ArXxv22001.05/44 1400
Zhao, J., Li, C., Wen, Q., Wang, Y., Liu, Y., Sun, H., Xie, X., and Ye, Y. (2021). Gophormer: Ego-graph transformer for node classification. CoRR, 101221100100..
13

---

A
Notation Table
Table 4: A summary of the notation used in this paper. The hat notation always refers to compressed network equivalent of vector matrix from the reference network.
Notation
Definition
The number of nodes in the graph
m
The number of attention edges in total, including graph and expander edges
d
Hidden dimension of narrow network Hidden dimension of the original large graph
D
L
The total number layers in the network
Arbitrary layer index
V
Value mapping of the vectors in the attention mechanism Query mapping of the vectors in the attention mechanism Key mapping of the vectors in the attention mechanism
Q
K
Weight matrix of mapping such as key, query, value, edge features, or bias in layer
(
Low dimensional network's weight matrix for mapping in layer
M
linear mapping matrix (usually from the higher dimension the smaller) Rectified Linear Unit
ReLU
H
Output of layer & from the reference network
H
low-rank estimation (())
H
Output of layer from compressed network column of matrix (()
h (
0
The Attention score between nodes and in layer /
The attention score between nodes and in layer from smaller network
B Dataset Descriptions
Below, we provide descriptions of the datasets which we conduct experiments. A summarized statistics of these datasets have been provided Table
Amazon datasets Amazon Computers and Amazon Photo are Amazon co-purchase graphs. Nodes represent products purchased. An edge connects pairs of products purchased together. Node features are bag-of-woe sor--ff-oor oordd encoded reviews of the products. Class labels are the product category.
Amazon2M Amazon2M dataset is graph from the co-purchasing network. Each node represents an item. Edges between items represents products purchased together. The node features are generated from the product description. The node labels are from the top-level categories the product belongs to.
Actor dataset The actor dataset is created by the actor-only subgraph of larger graph of actor, director, writer, and film co-occuring on a Wikipedia page, limited to Wikipedia page. Node features
films. Each
node corresponds
actor. Edges denote co-occurence based on the terms in the actor's page. The prediction task is categorizing into one of five categories (Pei al. 2020).
Coauthor datasets The datasets,, CS and Physics are co-authorship graphs from Microsoft Aca- demic Graph. The nodes represent the authors and an edge connects two authors who share paper. The node features are the keywords in the papers. The class represents the active area of study for the author.
ogbn-arxiv Huu et al. 2021) The ogbn-arxiv dataset is from OGBN datasets. The nodes represents the papers and edges represent the citations between the papers. Nodes are 128-dimensional feature vector that an average of the embeddings of words in the title and abstract. The prediction task is to identify the category of the 40 subject areas.
14

---

peobn-pooteis dataset The pronn-ptteins dataset is an undirected graph with edge weights and types based on species. The nodes represent proteins from eight different species. Edges indicate various biologically meaningful associations between the proteins (e-g., co-expression, homology etc.). The edges are eight-dimensional, with each dimension having a value from [0, indicates the confidence score. The prediction task is a multi-label binary classification among 112 labels to predict the presence of protein functions. The performance measurement is the average ROC-AUC scores across the 1 12 tasks.
Minesweeper The dataset is graph representation of the 100x 100 grid from the Minesweeper game. node represents a cell and the edges connect node to its eight neighboring cells. 20% of the nodes are marked as mines. The features of the nodes are the one-hot encoding of the mines among the neighbors. For 50% the nodes the features are unknown and indicated by a separate binary feature.
Tolokers Tolokers is graph representation of the workers in crowd-sourcing platform, called Toloka. Each node represents a worker. Two nodes are connected if the workers have worked on the same task. Node features are based on the worker's task performance statistics and other profile information. The task is to predict which nodes have been banned for project.
Pokec Pokec is a large-scale social network dataset. Nodes represents users of the network. Nodes features include profile data like geographical region, age etc. The task to predict the gender of users based on the graph.
Table S: Dataset statistics. The reported number of edges is the number of directed edges, which will be twice the number of actual edges for the undirected graphs.
Dataset
Nodes
Edges
Average Degree
Node Features
Classes
Metric
Amazon Photo
7,487
238,162
31.13
745
8
Accuracy
Coauthor Physies
34,493
495.924
14.38
8,415
Accuracy
Amazon Computer
13.381
491.722
35.76
767
10
Accuracy
Coauthor CS
18,333
163,788
8.93
6,805
15
Accuracy
ogbn-arxiv
169.343
2,332,486
13.77
128
40
Accuracy
Actor
7,600
33,391
4.39
932
5
Accuracy
Minesweeper
10,000
78,804
7,88
2
AUC'
Tolokers
11,758
1,038,000
88.28
10
AUC
Pokec
1,632,803
30.622.564
18.75
65
2
AUC
oghn-proteins
132,534
79,122.504
597.00
8
112
AUC
Amazon2M
2,449,029
123,718,280
50.52
100
47
AUC
C Experiment Details
C.1 Time-Memory Trade-off
One advantage of our method is that the time and memory can be traded without sacrificing the accuracy of the method. Figure 5 shows this trade-off on two datasets rybn-proteins and arxiv.
C.2 Hy perrparraeetess
In our networks, we use higher expander degree than what was used in the EXPHORMER paper. Since many of these edges will get small attention score, a higher attention score increases the receptive field of the nodes, letting the final network be able sample from wider options and have better access to long-range dependencies. We also noticed, the attention scores in the first layer are usually more flat than the other layers and so we usually sample more edges from the first attention layer. For the comparisons both on the results and the memory we have given the same expander degree to the Exphormer and the ogbn-arxiv dataset could barely fit into a 40GB GPU memory device with higher expander degree. For the attention score estimator network, we do not use dropout, and we only use one attention head these networks. The number of layers always equal between both networks.
15

---

optrrprllert chiiee
open-ara dalaset
110
430
1200
Time Spuch X0
33
230
1000
7500
2500
Dain San
(a)
(b)
Figure 5: The memory, nun-time trade-off for ogbn-proteinn proteins and aaxiv datascts. is worth mentioning that the experiments with different batch sizes yield similar results for accuracy/AUC. Memory and time can be traded in our approach.
We use A optimization algorithm in all our networks and use a cosine learning rate scheduler with it. We use weight decay of 1e - 3 in all networks. We use layer norm in attention score estimator networks to keep attention scores more meaningful, but use a batch norm for better results in the final SPEXPHORMER model. Other key hyperparameters can be found in Tables 6 and
Table 6: Hyperparameters used for training the networks for homophilous datasets.
Hyperparameter
OGBN-Arxiv Computer
Photo
CS
Physics
Attention Score Estimator
L
4
d,
8
4
4
4
4
Num Epochs
200
200
200
200
Learning Rate
0.01
0.1
0.001
0.002
0.001
Final Spexphormer Network
di
80
56
64
64
degr
[6, 6, 6]
[5, 5, 5]
[5, 5, 5, 5]
[5, 5, 5, 5]
[5, 5, 5]
Number Heads
2
2
2
Learning Rate
0.01
0.001
0.01
0.002
0.001
Num Epochs
600
150
100
120
80
Dropout
0.3
0.5
0.5
0.4
0.4
Table 7: Hyperparameters used for training the networks for heterophilic datascts. Hyperparameter
Actor
Minesweeper
Tolokers
Attention Score Estimator
L
4
4
d,
4
Num Epochs
100
100
200
Learning rate
0.01
0.01
0.01
Final Spexphormer Network
dz
32
32
32
deg,
[2,
2, 2]
[12,5,555]
[12,
10, 10, 10]
Number of Heads
4
4
4
Learning Rate
0.01
0.01
0.01
Num Epochs
100
80
200
Dropout
0.5
0.2
0.25
16

---

Table 8: Hypperparameters used for training the networks for the large graphs datasets.
Hyperparameter
ogbn-proteins
Amazon2M
Pokec
Attention Score Estimator
L de
2
expander degree
200
30
30
Num Epochs
150
150
150
Learning rate
0.01
0.01
0.01
Final Spexphormer Network
di
128
64
deg
[50, 30]
[10,10]
[20, 20]
Number Heads
Learning Rate
0.005
0.001
0.01
Num Epochs
200
200
300
Dropout
0.1
0.2
0.2
Batch size
256
1000
500
GPU Memory
2232MB
3262MB
2128MB
C.3 Hardware
For all trainings of the medium-sized graph datasets and the final network training of the large-sized graphs, we used GPUs of type A100 with 40GB memory, and V V100, both 32GB and 16GB versions. While these are powerful GPUs, we have always monitored the GPU memory usage for computational efficiency, ensuring that no more than 8GB is used for whole graph training and no more than 4GB of sizes.
GPU memory is used with batching. Training with even less memory is feasible with smaller batch
For caleulating the attention scores the large graph datasets, have used CPU devices Intel Xeon E5-2680 v4, with 500GB of memory. Except for the Amazon2M dataset, for the other datasets 200GB of memory would be sufficient.
D Theory
In this section, theoretically analyze the compressibility of the Graph Transformer architecture and also sparsification guarantees using the attention score estimator network.
For simplification, we use the following formulation of single head Transformer network:
degs
h1
(1+1/2)
(9)
1 ((+1) = w! (o ((()) (1
(1) exp (K(0) Q.1))
d1 EvENH(i) cxp (!(() 0!!7) (9)
where, V(0 W90 Q W000 K(O) = K M0, and can be any 1-Lipchitz activation function, such as ReLU, which has been used in practice in our networks. We re- move the normalization parts from the architecture but assume that in all steps for all vectors, ||X:l22 |/ (8+1/2) || [| ||2 < /a, and all linear mapping W. matrices' operator norm bounded by a constant 3. The first assumption is realistic because of the layer-norm applied between the layers in real-world architectures. The second assumption is also justified as the operator norms are near in the initialization of the network by the default Torch initialization and during the optimization
17

---

we expect the operator norm to not increase drastically from the initialization. Also, we assume h(() = X, which is the imput features. For a simpler notation, we will use D for a hypothetical large network hidden dimension in this analysis, and is the hidden dimension of the narrow network. For simplicity, in our analysis, we assume X E RnXD, In case each node has less than D features, we can concatenate them with zeros.
D.1 On the Compressibility of the Graph Transformer
Our approach uses a narrow network to estimate the attention scores. We want to show if we have a large network with good accuracy for task a graph, can work on the same input graph and the error of this network bounded by (e)) from the large network.
have less complex network that
The most memory/iime-intensii part of a Transformer architecture is its attention score calculation part. The rest of the sections are node/token-win and linear with respect to the number of nodes, The attention score estimation part of a Trln-Tranformer layer requires O(n d)) operations and O(md) operators required for sparse Transformer with attention edges. In the main Exphormer network, this would also more intensive as the edge features mappings require ((md)) operations, but since we replace edge feature mappings with edge embeddings by their type, this part in we do not have other edge features is (md), but m still can be w(n), and will be the most computationally-intenss
part.
Assume we have large network with L layers, where L is O(1), and hidden dimension D, we will show that there is similar network with L layers where the attention score calculation matrices
We. W K E I Dxd and all other matrices of the same size and d is O log"), ), where C is constant based on a and J. For this proof we use the distributional Johnson Johnson-Lindesn Lindenstrauss transform lemma (Johnson 1984):
Lemma D.1 (Johnson-Lindenstine Lindenstrauss Transform Lemma (JLT)), Assume 0 < e, < and any positive integer D, if = O 1oR(1/6)), there exist a distribution over matrices M E RdxD that for any x E RDD and ||>||| = 1:
Pr[| - 11> <
The following corollary is an immediate conclusion from the JLT.
Corollary D.2. Assume 0 < e, 8 } and any positive integer if 0 log (og(11/)) there exist
distribution over matrices M E IR that for any x, E D:::
Pr((1 +)((x - yll |Mr Myll (1 + e)|l= yll) <
This can derived by replacing x from JLT with
|
From this, can derive another corollary about the dot product of the vectors low-dimensional space.
1 and any positive integer D, if = Corollary D.3 (JLT-dot product). Assume O < e, < 2
O (loo(116) there exist distribution over matrices M IR that for any x, E RDD P, and
||=]| Ilvll S Va:
Pr((1 - -a)x < < M < (1 (1)ea)xT1)) <
For the proof see (Kakade and Shakhnarovich 2009, Corollary 2.1). As a result of this corollary, we have m pairs of vectors (x,, Wi), and for each | l|, llaulle S va of ya, and d = O log(m) there exists an M such that for all these pairs !a: M MMMy z! Vil < ea. The proof can be done using a union bound over the error from Corollary D.3 Also, our case where m the number of
edges, we know that m & n², thus we can also say O Iog(n))
Theorem D.4. Assume we have a Transformer network T with arbitrary large hidden dimension D, L O(1) layers, and in this network, in all layers, we have ||h.l12 S Va, and | W.llop S B.
18

---

There exists a Transformer T, that for any layer We and Wi are in RaxD for a d = 0 (m))))) with a sufficiently small E, and for all i E [n], IT(X), xx)) = O(e). And furthermore, for
any atlention score = 1 + (s))
Proof. In the proof we use hat notation, A. for the vectors and matrices from T, for example, () are the outputs of layer f, and W. are the weight matrices for this network. In all layers for both networks Wv, W1, and W2, are of the same size,
set Wy Wv. v. Wi W1, and W₂ W2-
For the proof, we want to find .(0),...., in a way that for any e in layer e. !n! h(6) e00, We will find these bounds inductively, starting from the first layer. We have e(0) 0, as both networks have the same input, and we want to bound g(f+1) based on e(()
We have Q (+)) w H9,, K(O w ( H and assume Q w H
K w 10 H
Q
Because of the operator norm matrices W and W K. for each i we have 11
(2)
q. 00 S e and
[ | I e(f) 3. Also, we have |lu| 1 I1 1I ( || S Bya, thus 11
0
S B(e + Va).
Now, for each pair of i and j, we have:
19.6% 9:
(9)
(0)
1 = 19:
1 ( 1
4.
q:
4.
S 19:
(6)
8
(
k2
(6)
q k
( 10
14 (
4 (0)
(
(K)
)
11 10 (0 (1
10 1 I 1
(0)
di
(1 + (Va + )
(V) + (3)
On the other hand, according the D.3 for E 1/2 and d O (llg(()) there exists
a matrix MΩK E D such that if we define Q09 = MΦx Q(1) and K (2) = MΦx K (f), b
1 (8 + (=()) (0) E for all (i.j) pairs in the attention pattern. w! Note that we can define ((()) Mox Q and w M w(O
l0!0
K both in R as weights for the narrow attention score estimator network. With a triangle inequality we have
10
< 2 (0) + (V + (0)
By setting (9) < 1, we have
10 1 (2)
< (a - +1 +
Let us define E. (a + 1+ 2/ + ()) we have:
expla!") (0) .2(()) 2,00)
exp(1 (2) -ko +Ea)
(0
S / exp(2sa)
(6)
Σ EMENT exp(g! (0) 1200)
Σ Ene exp(1; (6) k100) - -eo)
exp(1!") 2((0)
explg)" (1) -(00) Ea)
2 ajj (xp()2ee)
(
Σ EmENu exp(1!") 10) 1(00)
Σ EmENm(t) exp(g; (())
+ +.a)
||4 || (411/2) - h1 (6-11/2)
Now we bound
19

---

|1 (111122) 1
Σ jENei(()
16) (8)
1
Oig U/ 3/
=11 Σ
(6)
2, 0 10
/
jENNe(()
|| Σ
(
10
10 / |
)ENei(()
= [1(u))
(8)
+ t
(8)
Σ
(a))
jENei(1)
$ {110) 1/ + +111g,
Σ 10 dij
5 k0 V Σ max (1 - exp( - 22a), exp(2ea) 1)a
S 5 Va - 1),
and since 1+ + x < exp(x) < 1 + 2r for 0 < < 1, if we have Ea < 1, we have
||n ( h 12+1/2) s (1 4400..
(1)
For the feed-forward network part, know that this network is Be-Lipschitz because w and (((() have maximum operator norm 3 and a is I-Lipschitz activation function. Thus we have
|1 (1((tt)) - R ((+11) S (BE +4VaE.) (6 + 83a + (a) + (avaa + 2a + Va)e. Both 8 8ßa + 432 Va and 4,8 (ava 2a + va) constants, and if we define them as e₁ and C2 we have
((+1)) S sa + 628
Given (0)) = 0, as both networks get the same input, we have
(L)
S cie (1-1) + O2E
S a (c + c2E) + C2E
S <c2elct-1 +... c1)
cif 1)
C2 -
While the error increases exponentially with the number of layers, when we have L = 0(),, then the error is bounded by constant factor of chosen Now, we know that [IT((); -(())xla E(1) (e)).
While from the theorem it seems that the error is increasing exponentially by the layers, in practice the maximum number of layers used in this work is four with most large graph experiments using just two layers. Thus the constant factor will not be as large as it might look. Also, real-world graphs usually, the columns of X are not quite n distinct vectors and many vectors would be equal or very similar to each other if we have x unique vectors in the first layer the complexity for the can be reduced to O logg) ). In the homophily graphs the representations (*) tend to converge to each
other and thus again the number of unique vectors will be reduced letting us have smaller d, but these
assumptions are not considered in the proof as we keep it general.
Although we have proved the existence of the T, this does not mean that training with gradient- based algorithm will necessarily lead to the introduced weights, but this gives at least the guarantee
20

---

that such network exists. However, on the other hand, it is also possible that the training process finds weights that work better than the weights constructed in this proof.
Theorem D.4 by narrowing the attention score calculation part reduced the complexity from O(mD nD²) to (md nD²2,, and for dense graphs in scenarios add denser expander graphs, where m >> already the introduced network has much lower complexity. However, our narrow network uses narrow hidden dimensions in all steps and has complexity O(md + ndf). Proving the same guarantee along the whole network is not easy, if not impossible, without any further assumptions on X and the large network.
D.2 Analysis of the Sampling Process
After training a network with a smaller width d, we sample the edges from the original graph and use them in the second-phase training with large hidden width D. In this section, we shall analyze sampling process. Formally, we model our process as follows. Suppose that A is the attention score matrix with hidden width D, then sample and rescale entries of A to form sparse matrix B where the goal is the matrix B can approximate A well, i.e., | B x e||A||2. 2. However, recall that we can not access the entries of precisely. Instead, we consider another attention score matrix A', which corresponds to hidden width d.
The first question is how many samples indeed need to form the matrix B that approximates A well? To answer this, we have the following lemma for the attention score matrix A. Theorem D.5. Suppose that an n X n matrix A satisfies the following condition.
1. For each i, we have || 11 =
2. max, maxx =K
3. Each column A is E-sparse
Then, consider the sampling procedure that samples 8 2 8o = O(nK lognn(<2|1A11))) One (oenn/("" K)) entries of A with replacement
1. For each sample Br, the probability that B, samples entry Asg is = (with a rescale factor L/Psg. i.e., B. Aig/Pis). and each B, only sample one entry of A.
|A
= Aigl
|
2. Form the matrix B = (Bi + B2 + + B.)/s
Then, we have that with probability at least 9/10,
A BlI2 =||A||2.
To prove this lemma, we need the following Matrix Bersiten inequality. Lemma D.6 (Matrix Bersiten inequality). Consider a finite sequence X, of ii.d random where E [XX and || 2l I R. Let a² = max max{[[E]] [||[[[]XX]]] XT]] [[[ X, X,]l For some fixed 2 1, Let (X1 + X2 + Xx)/s, then we have that
88*
X||
(m + n) exp
(- Re/3
Proof. We follow similar proof strategy in Achlioptas et al. of Achlioptas et al. (2013) considers the matrix Bernstein inequality where have the tail bound
2013). At a high level, the work
sEa
Pr[]A- BII2 2 s] < 2n exp
x2+ Ro
dependent on the following two quantities
max { [| B:)(A - BI) [E[ BA) B1)]
R max| - B1ll over all possible realizations of B
21

---

Where B1 is the matrix that only samples one entry and the final output B = (B1 B2 + ... ............. -+ +B,)/s.
Then, instead we consider the following quantity,
0² max
max Σ
Azg/ Pij. max
Σ EAgl/Prs
R max Atyl/Pps
shown in Lemma A.2 of Achlioptas et al. (2013) we have that 10/ō 1 $ Σ. Al
and
|R/R R 1|
||l and from the condition of the matrix A we have both of the upper bounds
1
most Hence, we only need to consider ē and R. Back to our case, we have that Pij = 1 |4,
TAayl
1. Aggl from this and the assumption of A we have
8² = n. max
max Σ Aiyl. max
Σ Auil
I In.K K
R max A1s k/i/
Hence, to make 8 < 0.1, we only need to set E' = =||A| lz in the Matrix Bernstein inequality and then we have 2 OnK logn/(="|| Finally, note that if || = K, then we have ||-|]22 2 ||Ae,l2 || 1| 2 K/VE, which means that n.K' log (c || I nf log n/)²k).
However, as mentioned, we can not access the value of the entries of A but the entries of A' (which corresponds to the trained network with small hidden width d). We next show that even in the case where we sample the entries of A from A', we can still get the same order of the bound the entries of A are not under-estimated seriously in A'.
Proposition D.7. Suppose that the matrices A and A' satisfy the condition in Theorem D.5 and for every j we have
|4, -
for some sufficiently large constant a. Then consider the same sampling procedure Theorem D.5 but sampling the entries of from the value of A'. Then, the guarantee in Theorem D.5 still holds.
Proof. We only need to note that from the assumption, the actual sampling probability Ptj 2 a Psj in Theorem D.5, hence it will increase the 8² and R by most a times, which means that we can increase by an a factor to make the error probability at most 0.1.
E
Discussion
Graph datasets arise from various domains, meaning that they might have differing inductive biases. More expressive methods may not necessarily yield better results on all datasets (Franks et al. 2024). Depending on the architecture and the task, more complex models can even lead to poorer results. Here, we discuss possible scenarios in which our model can be good fit as well as the shortcomings of other classes models that are overcome by our model.
Graph Structure The relevance of the structure of the graph to the task can vary. For the simple synthetic task introduced [ the structure of the graph does not matter. So Transformers without inductive biases of the graphs are expressive enough to solve this problem; however pesssag-ppassigg networks will be restricted to the graph edges and rely on enough number of layers and may be challenged by oversquashing and oversmoothing problems. On the other hand, if the structure of the graph matters, such as counting the number of neighbor nodes with same color for each node, the structure and the edges will be an important part. Transformers without expressive enough encodings to identify the graph edges will fail this task. On the other hand, MPNNs even with one layer can casily solve this problem. Our approach enables solving problems in either case, by having both
22

---

expander graphs for universal information propagation and the actual graph edges for inductive bias, allowing the model decide the subset of edges that suit the task better only graph edges, only expander edges or combination of both.
Short-range Vs. Long-range Dependencies If the neighboring nodes tend to be from the same class, i.e., high homophily, MPNNS and methods such as NAGphormer (Chen et al.) (2022a), which summarize the neighborhood have good inductive biases; whereas Transformers without proper identification for the neighborhoods may not be as fit for this task. Heterophily may not necessarily mean long-range dependencies, label of each node may just depend on the neighbor nodes, but still label of the neighbor nodes may be different most of the time. For example. for finding the grammatical function of the words in a sentence from a very long text, neighboring words are usually enough for this identification, and nearby words would be from different classes. On the other hand, some tasks may require long-range dependencies - identifying if there are other people in a social network with similar interests the synthetic task introduced in T are some examples. Local models such as MPNNs would require deeper networks for modeling long-range dependencies that makes them prone common problems such oversquashing and oversmoothing Topping al., 1 Di Giovanni et al., 2023b |Rusch et al.] 2023). Our approach can be reduced to MPNN by giving lower attention scores to the expander edges, for learning on the tasks with short-range dependencies only. And also lets the long-range dependency modeling using expander edges. While models designed specifically for some of these tasks may have the advantage of reduced complexity. But our approach lets learning without concern about the nature of the problem or having domain knowledge for the task or graph.
Subsampling Graphs Many approaches break the graph into sections or subsample nodes or neighbors for training. This approach has shown promising results in many works such as (Zeng et al. 2020; [Hamilton et al., [2017] Liu et al., [2021). However, there are many cases in which these approaches are not expressive enough. Clustering the nodes or batching and subsampling based on the neighborhood will not have the required inductive biases to solve the tasks with long-range dependencies. Approaches such as neighbor sampling or connected -ubgrraph sampling not only inherit the limits of the MPNN networks. but may even miss short-range dependencies. For example, Example (c) in [T] by merely random selection of the neighbors or subgraphs without considering the task. Random subset of node selection that has been used in several promising papers such as Wu et al. (2022 2023 2024) gives a chance for nodes from the same label to appear in the same batch, but the batch-size should increase with the graph size accordingly. Very small ratio of batch size to graph size would mean many edges or possible pair of nodes will never be appear in any batch and depending the task this can limit the power of these models. Also, these models are usually not memory efficient, as graph size grows, they can not keep the batches small, and the required memory grows accordingly. On the other hand, our approach (1) makes smarter selection of neighbors based on the small network's 's attention scores; (2) our sampling allows making k-hop neighborhood subgraphs from the extended graph connectivity, and (3) allows the training by trading off memory and time, without critical harm to the model's expressive power. Unline the GraphS AGE and SGFormer, which use the full graph for the inference time our model uses the same sampling and batching techniques, letting efficient inference beside the efficient training.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipp/.cc/pullc//uuui wwwiiicgguie//eeeeeeeeeic CoodeSubeiiie ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
26

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[No]
Justification: No specific societal impacts as opposed to other graph neural network models are expected.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
27

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our model does not fit in high-risk or misusable models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
28

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "7vRVcB3DRS", "reviewer": "Reviewer_UFNp", "summary": "This work studies the topic of sparsifying Graph Transformers which if quadratic is not scalable even on medium sized graphs. It builds on recent works like Exphormer, GraphGPS, SAN, among others and proposes a new two stage procedure with the naming Spexphormer. It is designed to reduce memory complexity for node classification tasks. The two stage process helps improve the scalability limitations of existing work such as Exphormer. First, a narrow network is trained on a fully augmented graph to estimate attention scores and these are used without edge features. These attention scores are then used to train a wider network on a much sparser graph. Experiments conducted on 11 datasets show that Spexphormer achieves competitive accuracy with lower memory usage.", "questions": "- Although the sparsification is addressed, the two stage process can be complicated to implement without expertise. Moreover, the reliance on the first narrow network could mean error propagation to the actual model. The paper mentions this limitation and provides a study for the approximation in 5.1. However, it may not be true universally.\n- The experiment section shows reduced memory usage for the smaller datasets, and in generally the maximum node size of datasets used is in ~2 million range. I would be curious to see the trends on the datasets of Table 2, eg. Amazon2M products dataset.\n- In section 4.3 and later in appendix, it seems the approximation aspect is studied for the first layer only, which makes it for simplification, understandably. What are the implications of this with respect to layer wise sparsification in terms of the approximation guarantees?\n- Writing format: For better readability, the Figure 4 can perhaps be placed appropriately before the experiments as it relates to the motivation of the method.", "limitations": "Yes the paper discusses the limitations of the method in the work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The question of how can graph transformers be further made scalable - through sparsification - is addressed. Although there can be multiple directions to scale the network which are discussed in the literature review section.\n- The two stage training forms the basis of sparsifying the graph even further than Exphormer. While doing this, there can arise several challenges. These challenges are touched upon by the paper to a decent extent.\n- Experimental analysis shows a clear reduction in the memory usage of the proposed Spexphormer with the base model.\n- The method follows a theoretical justification of why the approach of sparsification makes sense, though with assumptions.", "weaknesses": "together with Questions below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback! Here you can find our response; we also encourage you to check our rebuttal pdf for some new experiments.\n\n> the two stage process\n\nEven for one-stage training, hyperparameter tuning is a significant part of the training. In our setup, the first stage is relatively easier to tune — we only need one training run that converges from the initial network, and as the number of layers and the hidden dimensions are fixed, usually just tuning the learning rate works. So the “overhead” of training two networks is not so huge, compared to the usual process of hyperparameter tuning. We think this plus the additional extra complexity – mitigated by us releasing documented code for the two-stage pipeline – is not so extreme, and often worth it for the benefits it brings.\n\nAlso, the training process of the second network is independent of the initial network given the attention scores. We intend to share the attention scores we have from our initial network’s training publicly for possible future uses.\n\n> error propagation\n\nIt is true that the error can propagate. However, this is not too drastic because the second network learns its own attention scores. The neighborhood sampling is done with the initial network, and the second network just gets the updated list of the neighbors and learns its own attention scores. As long as the initial network gives reasonably high attention scores to important neighbors, the second network can adjust the attention scores. Even if some of the selected neighbors are not very informative, the second network can ignore them by giving a lower attention score. \nIf an informative link is missed, it is likely that the needed information can propagate through other (longer) paths. Also, different neighborhood sampling per Transformer layer helps to mitigate the possibility of missing important links.\nEven if some of the important neighbors are underestimated in the initial network, increasing the number of sampled neighbors can also help bring them back to the sampled neighborhood.\n\nOur experimental results in Table 1, compared to Exphormer, show that the total amount of introduced error is not that large, and our approach can give competitive results.\n\n> The experiment section shows reduced memory usage ...\n\nIn Figure 3, the memory has been reported from the actual running of the methods for smaller datasets. It is not feasible to train the original Exphormer on a 40GB GPU even with only 1 layer and hidden dimension of 4 or 8. Among the tested datasets, the largest feasible for Exphormer is ogbn-arxiv, where we see a ~5x reduced memory usage. The memory savings is considerable even without any batching.  Training the model with two layers and hidden dimension 8 requires near 200GB for Amazon2M dataset; training it with the hidden dimension 256, and without advanced techniques that trade memory and time, requires between 32 (256/8) to (32)^2 times more memory, which is not feasible even with most CPU devices.\n\n> theory\n\nIndeed, this is a limitation of our theory at time of submission. Since submission, we’ve continued to work on that, and have been able to extend the result to deeper layers for a scheme similar to (but not the same as) the narrow network we use in practice: a narrow attention dimension, but dimensions for the other parts of the network (e.g., the MLP layers) the same as the target network. (This “in-between” scheme saves in the most expensive part of the network.) The result is as follows:\n\nTheorem: ​​Assume we have a Transformer network $\\mathcal{T}$ with arbitrary large hidden dimension $d_l$, $L=O(1)$ layers, and in this network, in all layers, we have $\\lVert h_\\cdot\\rVert_2 \\leq \\sqrt{\\alpha}$, and $\\lVert W_\\cdot \\rVert_{op} \\leq \\beta $. There exists a Transformer $\\widehat{\\mathcal{T}}$, that for any layer $\\mathbf{W}_Q$ and $\\mathbf{W}_K$ are in $\\mathbb{R}^{d_s \\times d_l}$ for a $d_s=\\mathcal{O}(\\frac{\\log n}{\\epsilon^2})$, with a sufficiently small $\\epsilon$, and for all $i \\in [n]$, $\\lVert\\mathcal{T}(X)_i - \\widehat{\\mathcal{T}}(X)_i\\rVert_2 = \\mathcal{O(\\epsilon)}$. \n\nThe proof idea is to use Johnson-Lindenstrauss for the attention scores, bound them by relative error, and then bound the Euclidean distance of the other vectors based on the errors happening in the attention scores. The difference here with the previous proof is that the error can propagate from the Euclidean distance from the input of the layer too. But, we bound all these errors and show that the total error is still $\\mathcal{O}(\\epsilon)$.\n\nThis proof only works for narrow attention score estimation, and assumes the other parts of the network have the same dimensions. This is, however, the most memory/time-intensive part of a Transformer architecture. The rest of the sections are node/token-wise and linear with respect to the number of nodes. The attention score estimation part of a full-Transformer layer requires $\\mathcal{O}(n^2d)$ operations and $\\mathcal{O}(md)$ operators are required for a sparse Transformer with $m$ attention edges. Thus this change effectively changes the computational complexity of the model.\n\nAlso, another interesting thing about this proof is that it not only shows that there is a network with similar attention scores but narrow attention calculation hidden dimension; but also by bounding the error in the output, it shows that this network is nearly as good as the large one, and thus if the large network is optimal, this would be at least near-optimal network in the lower dimension.\n\nThis expanded version of the theorem helps extend our guarantees about the possibility of approximation to deeper layers. Thank you for pointing out this important issue.\n\n>Writing format\n\nWe very much agree with this comment and we will definitely move that figure for the next revision.", "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": "", "extra_scores": {}}, {"review_id": "tfIc22JqAy", "reviewer": "Reviewer_X47Y", "summary": "This paper proposes a method to reduce the memory complexity of Exphormer's transformer layers by learning a sparser attention pattern. Given some graph learning tasks, the authors first train a small-width, single-head proxy model on CPUs with large memory resources. After training, the attention scores of the smaller proxy model appear to reflect which interaction edges in Exphormer's attention network are important to solve the given task. These attention scores are used to sample (in a layer-wise fashion) sparser, regular subgraphs of the original interaction graph. These give rise to layer-wise sparse attention patterns which can be used to train a larger model on GPUs with constrained memory resources. This allows scaling Exphormer to larger graphs.", "questions": "- The paper focuses on memory consumption for small graphs. It's expected that Spexphormer's benefits would be most significant on large graphs. To strengthen the analysis, consider estimating Exphormer's memory consumption on large graphs (e.g., by running a single training step on CPU).\n- The paper claims a complexity reduction for Spexphormer layers, from $\\mathcal{O}((m + n)d^2)$ to $\\mathcal{O}(nd^2 + ndc)$ (Eq. 31 & Eq. 77). This improvement hinges on $c$ scaling sublinearly with the average node degree. While theoretical indications for this possibility are mentioned, are there empirical results supporting it?\n- Section 4.2.1 suggests that Spexphormer allows for memory-efficient batching due to slower subgraph growth compared to Exphormer (line 42). Has this advantage been evaluated experimentally?\n- The claimed complexity of $\\mathcal{O}((m + n)d^2)$ for Exphormer layers (line 31) is unclear. The Exphormer paper's discussion is also missing. Specifically, why is there an $md^2$ term instead of $md$ (there are $m$ dot products between d-dimensional vectors)? Additionally, why does the $d^2$ term change to $d$ in the Spexphormer complexity (line 77)?\n- Typically (including Exphormer), the equation would be $\\mathbf{V}^j_i = \\mathbf{W}\\_o \\mathbf{W}^{j}\\_{V} \\mathbf{X}_{\\mathcal{N}_H(i)} $ where $\\mathbf{W}_o \\in \\mathbb{R}^{d \\times m}$ and  $\\mathbf{W}_V^j \\in \\mathbb{R}^{m \\times d}$ and $m$ is the head dimension. This serves to reduce the parameter count. Is this also the case for you and just an accidental omission, or are you actually learning several $d \\times d$ matrices $\\mathbf{W}_V^j$?", "limitations": "While the authors identify high main memory usage as a limitation, a more comprehensive analysis of limitations is warranted. Here are some key considerations:\n- **Efficiency of attention implementations:** The paper doesn't explore the potential benefits of using efficient attention implementations like FlashAttention, which could potentially achieve similar memory savings as the proposed method. Evaluating Spexphormer's performance with such implementations would be valuable.\n- **Impact of Expander degree:** The evaluation compares Spexphormer to an Exphormer baseline that uses a higher expander degree than the original Exphormer paper. This potentially favors Spexphormer. A more balanced comparison would involve evaluating Exphormer with the original degree to understand if it suffers from the same memory limitations.\n- **Runtime considerations:** The evaluation focuses solely on memory consumption, neglecting the potential impact on runtime. Since runtime can be traded off for memory, it's crucial to analyze how Spexphormer affects runtime performance.", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "- It seems that the idea of using smaller proxy models to find sparse attention patterns is novel. Given that this approach could also be applicable to other domains, it may be relevant to the community.\n- The authors appear to have some theoretical results motivating their method.", "weaknesses": "- The paper claims that graph transformers typically suffer from quadratic memory complexity. While this holds true for dense attention mechanisms (including self-attention), efficient implementations like FlashAttention achieve linear complexity. The authors do not explore such implementations for their sparse attention approach, which could potentially lead to similar benefits. Notably, while the sparsity pattern itself requires $O(|E|)$ memory, it's unclear whether its storage dominates the memory usage compared to the potentially inefficient computation of attention scores as seen in Exphormer (e.g., [here](https://github.com/hamed1375/Exphormer/blob/1b43962bd418fcb7faf98f7b34e3b165ba833fb6/graphgps/layer/Exphormer.py#L46)). A more in-depth discussion on this trade-off would be valuable.\n- Furthermore, the evaluation focuses solely on memory consumption, neglecting runtime performance. Since runtime can be traded off for memory (e.g., via activation checkpointing), the authors should analyze the runtime implications. If the proposed method increases runtime, a detailed justification explaining the memory-runtime trade-off compared to existing approaches is necessary.\n- A potential bias in the evaluation is also observed. The authors use a higher expander degree (deg=30) compared to the original Exphormer paper (deg=6). This choice reportedly benefits their method (as noted in lines 524-526). However, the Exphormer baseline also uses this higher degree (lines 205-206). It's crucial to investigate how this skews the results and whether Exphormer with the original degree would have similar memory limitations.\n- Regarding Table 2, where Exphormer runs out of memory, stronger baselines are needed. For instance, Polynormer [1] might outperform Spexphormer on the pokec dataset. Additionally, studies like NAGphormer [2] that evaluate stronger baselines on pokec could provide evidence that even GCN might outperform Spexphormer.\n- To further validate the effectiveness of the proposed proxy models, including a baseline with random sparsification would be beneficial. This would demonstrate that the proxy models offer an advantage beyond simple pattern reduction.\n- The baseline distributions in section 5.1 appear overly simplistic. Utilizing distributions based on the actual models' behavior would provide a more realistic picture.\n- Ablation studies investigating the impact of value normalization (line 212) and variable temperature (line 218) would be insightful.\n\n### Minor Points\n- Appendix B: This seems to contain verbatim citation. It also appears like this in the Exphormer paper, but I do not know whether that is the primary source. I think one should mark appropriate paragraphs as verbatim. \n- l162-l165: I feel like this is making a strong claim (\"$\\mathbf E^j$ is insufficient\") with a very lax argument (\"\\[assuming\\] the columns of $\\mathbf K$ and $\\mathbf Q$ are distributed independently and uniformly....\"). I would consider removing this strong claim or adding an ablation that supports it.\n- l242-250: This paragraph is quite unclear. The phrasing \"almost the same features\" and \"lead to the same result\" are too unspecific for a research paper, even if one can infer what is meant. Overall, the paragraph seems to try to give an intuitive understanding why sampling should be better than selecting the top-k neighbors. Unless there are experimental results to support it, I am skeptical whether one should make the claim that one is better than the other.\n- In the equation in l142-143,some information regarding dimensions and the meaning of $\\sigma$ could be helpful to readers.\n- Big Bird appears twice in references (l467, 470). Similar issue in lines 460, 462\n- Landau symbols are not typeset consistently (sometimes `\\mathcal` is missing)\n- l180-181: Being pedantic: it probably is possible to fit the transformer on the GPU, but it is not possible to train it. \n- l251-252: What does \"exponentially large\" mean?\n- l258-259: Do you mean $\\mathcal O(|\\mathcal{N}_H(i)|)$ complexity?\n- l259: what do you mean by trial and error?\n- l268: no space after comma\n- l289: I assume it should be $|\\mathcal{V}_l|$ instead of $|\\mathcal V|$\n- l511: socal -> social\n- l536: missing reference\n#### References\n[1] Deng, C., Yue, Z., & Zhang, Z. (2024). Polynormer: Polynomial-Expressive Graph Transformer in Linear Time. ICLR 2024\n\n[2] Chen, J., Gao, K., Li, G., & He, K. (2023). NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs. ICLR 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your very thorough review; sorry for brevity (character limit). Please also see rebuttal pdf for updated results.\n\n> quadratic memory complexity\n\nFlashAttention computes either full-attention or sparse-block attention mechanisms, with memory-aware loading of relevant parts of data. The use of full-attention, block-sparse attention (Big Bird), or linear approximate attention mechanisms (Performer) has been explored in the GraphGPS paper; Exphormer usually gets superior accuracies, probably thanks to its inductive bias.\n\nA full-graph transformer with FlashAttention should work (with somewhat-worse accuracy expected), but would highly rely on positional encodings, standard versions of which are difficult to compute for large graphs. This is a feasible model to explore, but would require significant innovation and be very different from our work.\n\nThe block-sparse version of FlashAttention without considering the structural biases of the graph seems a poor fit for graph structures (cf BigBird results from GraphGPS).\n\nDoing FlashAttention on an Exphormer-type attention pattern seems inefficient, since the block structure seems important to FlashAttention's efficacy, while Exphormer-style graphs can have nodes of wildly varying degrees (if the original graph’s degree varies, as usual).\n\nSomething like FlashAttention might be more feasible on regular graphs, as from Spexphormer. But this potential computational improvement to our approach seems to require deep thought about GPU memory structures and difficult implementation work, as did FlashAttention; we don't think this should be necessary for an initial paper exploring a new approach.\n\n> evaluation focuses solely on memory\n\nWhere we can train the original network, our approach is faster than Exphormer in general. For Photo, Exphormer takes 1.7s/epoch, our initial network 1.1s/epoch, final Spexphormer 0.5s/epoch. For Tolokers, Exphormer takes 6.2s/epoch, our initial network 4.6s/epoch, final Spexphormer network 1.1s/epoch. This advantage is larger for denser graphs. We also have added some experiments on the trade-off between RAM and GPU, as we can trade-off memory and time without any advanced GPU-level implementations (Figure 2 in rebuttal pdf).\n\n> potential bias in the evaluation\n\nEven using a smaller degree Exphormer uses much more memory than our higher degree Spexphormer, see Fig 1 in our pdf for some numbers. Since Spexphormer can effectively use these higher degrees, it is more likely to be able to handle long-range dependencies. For example, in the ogbn-proteins dataset, an expander degree of 30 barely achieved an AUC of around 0.78 with a thorough hyperparameter search. Increasing the degree to 200 yielded an average AUC of 0.806.\n\n> Table 2 ... stronger baselines are needed\n\nThanks for highlighting this. We mostly followed the experimental setup + setup code from SGFormer; while they state they use the standard 80-10-10 train-val-test split, we had not previously noticed that their code (and ours) actually uses a 50-25-25 split. The numbers in Table 2 are correct for this split, but exacerbate the difference vs Polynormer due to smaller training set; eg SGFormer's GCN has accuracy 62%, while Polynormer's is 75%. We only just realized this, and are rerunning with the standard split; we'll try to provide numbers before the discussion period ends.\n\nIt's also worth noting Polynormer uses many more parameters than our models: 7 local + 2 global layers, each with hidden dimension 512, compared to our 2-layer network with hidden dimension 64. They train with batching based on a random subset of nodes, which as mentioned in Figure 4 and Appendix E can fail catastrophically; on Pokec in particular, though, the neighborhood summary is the most important feature, and the graph structure is not especially relevant, so this does not hurt much.\n\nThe idea of polynomial layers is also possible to directly drop in most common architectures, including ours; a SpexPolynormer combination model would be straightforward to write down. Their added complexity and hyperparameters, however, including a warm-up phase, mixture of global and local layers, etc. makes this cumbersome to include when exploring other new ideas.\n\nAlso, all of our current large-graph experiments now run with under 4GB of GPU memory, showcasing that our approach works well with very small batch sizes – unlike random-subset approaches which do not scale to small batches. (See the rebuttal pdf for more.)\n\nMoreover, our first phase of training uses high CPU memory, but later training and evaluating the learned model on a given node can be done with low memory. Pollynormer, SGFormer, even GCN all batch for low memory during training, but evaluate with high CPU memory (loading the whole graph). \n\n> Baseline with random sparsification; baseline distributions appear overly simplistic\n\nAlso, uniform neighbor sampling is a common approach, used famously eg in GraphSAGE which often gets competitive results. In Table 1 of the pdf, we see using our network instead of random sparsification helps a lot in some datasets.\n\nWe’re not sure what you mean by “distributions based on the actual models’ behavior,” other than exactly the distributions that we use in Spexphormer. Do you have a specific baseline in mind to compare to?\n\n> Ablation studies\n\nGood idea; also in new Table 1.\n\n> Appendix B\n\nThanks for noticing this; sorry for the mistake which we overlooked in submission. We will rewrite this section.\n\n> l162\n\nOur claim is not that it is _always impossible_ (though it is at initialization) for a model to decide to e.g. ignore expander edges, but that bias variables make it much easier. We’ll clarify.\n\n> l242\n\nYou are correct that we are making an intuitive argument for why we chose sampling over top-k selection; we'll clarify.\n\n> Other minor points\n\nThanks; we'll fix these.\n\n> Questions\n\nPlease see the separate author response above; thank you for your detailed review!", "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": "", "extra_scores": {}}, {"review_id": "a3sAe7Pzbh", "reviewer": "Reviewer_vT4j", "summary": "This paper proposes a two-phase training process for Graph Transformers to address the memory and computational inefficiencies associated with large graph datasets. The first phase involves training a small-width network to estimate attention scores. These scores are then used to construct sparse interaction graphs for a larger network, which is trained in the second phase. The authors claim that this approach maintains performance while significantly reducing memory requirements. They provide theoretical justifications for their sparsification method and validate their approach through experiments on various graph datasets.", "questions": "The authors claim that the fixed number of neighbors for each node enables matrix multiplication calculations instead of edge-wise calculations (gather operation), improving the speed of the model. I would like to ask how much faster this approach is in terms of training time compared to Exphormer and MPNNs?", "limitations": "Limitations are discussed.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is generally well-written and structured. The methodology and experimental setups are clearly explained, making it easier for readers to understand the proposed approach.\n\n2. The paper introduces a novel two-phase training methodology. This approach is creative and has the potential to address a significant limitation in current graph transformer models related to scalability and memory usage.\n\n3. The theoretical analysis provided in the paper gives a solid foundation for the proposed method.", "weaknesses": "1. While the two-phase training process is innovative, it primarily builds on existing Exphormer. It mainly adjusts the flexibility of the expander graph and adds a sampled attention mechanism. The novelty might be seen as incremental rather than groundbreaking.\n\n2. It was recently shown that the reported performance gap between Graph Transformers (GTs) and MPNNs on node classification is overestimated due to suboptimal hyperparameter choices [1,2]. My concern is whether we truly need global information propagation for node classification in large graphs and whether models need to approximate a full Transformer. Currently, from an experimental perspective, MPNNs with residual connections outperform GTs, even basic models like GCN or GAT. In this context, the authors need to compare the memory usage and runtime of MPNNs and the proposed method to demonstrate its efficiency.\n\n   [1] Bag of Tricks for Node Classification with Graph Neural Networks.\n\n   [2] Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification.\n\n3. The authors are encouraged to include an ablation study to clarify the necessity of the two-phase training process. This study should illustrate the effects of not utilizing a wider network trained on a much sparser graph.\n\n4. The theoretical analysis is primarily focused on the first layer of the network. It would be more compelling if the analysis were extended to deeper layers to provide a more comprehensive understanding of the method’s effectiveness.\n\n5. Minor Issues: Lines 268-277 are somewhat confusing, particularly line 275, where the number of query nodes might be incorrect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable review. Here are our responses. Please also refer to the rebuttal PDF for some extra tables and figures.\n\n> Innovation\n\nAs mentioned in lines 97-102, we use Exphormer to interpolate between MPNNs and full-attention Transformers. Lower expander degrees make the model similar to MPNNs (particularly, eg, GAT), and the highest degree (n-1) will be equivalent to full Transformers. None of our theory relies on the expander degree or even the existence of the expander graph, and the experimental results include expander degrees from 30-200. The main idea of our work is to make a sparse and scalable method, and it made sense to start from an already sparse method such as Exphormer, and build on it to sparsify further. Sparsification from the full Transformer can be a little tricky, because the attention scores can be very small and unreliable (because of the large number of nodes to attend).\n\nIn addition, our paper has other contributions of additional interest, such as the batching technique (a particular fit for our sparsification, but usable in other settings), and our theoretical results regarding the compressibility of the network.\n\n> Comparison with GNNs\n\nThanks for pointing to these papers. The second paper mentioned here was published after our submission, and so we were not aware of it before submitting. However, there are a few important things to consider:\n\n- The networks they have used for their experiments are much larger than the ones used in our work, in the sense of the number of parameters. For example, for Minesweeper they use 15 layers with hidden dimension 512, while we use four layers with hidden dimension 32. We also have focused on the memory efficiency, and most of the small datasets are trained with less than 4GB GPU limitation. Their models have been trained on a workstation with 8 RTX 3090 GPUs (each of which would typically have 24GB of memory).\n\n- While our work is focused on memory efficiency, we also do batching based on the task and the requirements of the problem (relying on the attention scores from the initial network). However, these works need to train their method based on random subset selection batching, which as shown in our Figure 4 and Appendix E can sometimes behave very poorly. As the ratio of the batch size to the whole graph goes to zero for a fixed-degree graph, the probability of ever seeing any edge in the training process also goes to zero. By contrast, our batching is independent of the ratio of the graph size/batch size, and allows trading off time and memory without biasing the gradients of the problem parameters.\n\n- These GNNs are well studied for many years, and Graph Transformers are relatively new. Thus, there is probably also potential to also find new tricks that improve GT performance. Many key advantages of the GTs can also be brought to the GNN world, as most of these things appear in the papers you have mentioned. The long-range dependencies can be handled by deeper GNNs, and oversmoothing/oversquashing and simplistic message functions can be handled by residual connections, jumping knowledge, layer normalization, and larger hidden dimension. Even so, much smaller GTs “naturally” handle many of these problems, and so the potential for better performance by finding appropriate tricks seems solid.\n\n> Ablation studies\n\nThanks for this suggestion; we have added an ablation study including this in our rebuttal pdf.\n\n> The theoretical analysis\n\nIndeed, this is a limitation of our theory at time of submission. Since submission, we’ve continued to work on that, and have been able to extend the result to deeper layers for a scheme similar to (but not the same as) the narrow network we use in practice: a narrow attention dimension, but dimensions for the other parts of the network (e.g., the MLP layers) the same as the target network. (This “in-between” scheme saves in the most expensive part of the network.)\n\nBecause of the space limitation in this reply, please refer to [our response to reviewer UFNp](https://openreview.net/forum?id=K3k4bWuNnk&noteId=JyboPAF7sR) for the details.\n\nThis expanded version of the theorem helps extend our guarantees about the possibility of approximation to deeper layers. Thank you for pointing out this important issue.\n\n> Minor Issues\n\nThanks for mentioning this. We will fix the mistake and make the writing more clear for the next revision, as well as adding pseudocode to clarify.\n\n> Speed improvement\n\nTo give you some examples, the training time per epoch for the Tolokers dataset when training on the sparsified graph improves from 0.56s to 0.47s, and for the Photo dataset, it improves from 0.43s to 0.36s on average. This is a significant improvement, considering that many other parts of the network, such as Q, K, and V mappings and the feed-forward networks, are fixed and have similar overhead in both cases, with only the attention score estimation part changing.\n\nThe time improvement is even more considerable when comparing the Exphormer model to our sparsified regular graph. For example, the whole epoch time (neighbor sampling + training + validation) improves from 6.2s/epoch to 1.1s/epoch on the Tolokers dataset, and from 1.7s/epoch to 0.5s/epoch on the Photo dataset.", "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": "", "extra_scores": {}}]

Author rebuttal:
# New experiments

All reviewers: please see the PDF linked below, which has some new experimental results.

# Further response to Reviewer X47Y

Due to character limits in responding to your very thorough review, these are continued here; thanks again for your work in reviewing our paper!

> To strengthen the analysis, consider estimating Exphormer's memory consumption on large graphs (e.g., by running a single training step on CPU).

We use 200GB of memory to train on a dataset such as Amazon2M with only hidden dimension 8. Training the network with hidden dimension 256 would require at least 32 times the memory, which we did not have available, even on CPU. Alternatively, the memory and time could be traded here, as you mentioned earlier, but training for 150 epochs with hidden dimension 8 takes almost a day; checkpointing or similar techniques could easily make the training take a week or more.

> The paper claims a complexity reduction for Spexphormer layers, from $\mathcal O((m+n)d^2)$ to $\mathcal O(nd^2+ndc)$ (Eq. 31 & Eq. 77). This improvement hinges on c scaling sublinearly with the average node degree. While theoretical indications for this possibility are mentioned, are there empirical results supporting it?

Spexphormer improves this asymptotic complexity if $m > n c$, or $c < (m/n) = \rho$, where $\rho$ is the average degree of the graph. This is in fact always the case in our setup. If we want to have the benefit of the expander graph, a regular expander graph of let's say degree $k$ would be added; in all our experiments $c < k$, and thus it is guaranteed that $c < \rho$. In most cases we also have $c < \rho - k$, if we considered not using the expander graph at all. $c/\rho$ values are as low as (0.08, 0.05) for the two layers of Proteins, and on average around 0.1 for the homophilic datasets in Table 1.

In addition to the lower degree, the regularity of the sampled graph helps with avoiding many complexities from varying degrees in the nodes, helps with the batching process and more efficient calculations as mentioned in section 4.2.2.

> Section 4.2.1 suggests that Spexphormer allows for memory-efficient batching due to slower subgraph growth compared to Exphormer (line 42). Has this advantage been evaluated experimentally?

When $c$ is smaller than the expander degree $k$, as usual in our work, the neighborhood expansions are strict subsets of those from Exphormer. We haven't yet done explicit experimentation on this but will try to do so during the discussion period, or else for the revised version.

> The claimed complexity of O((m+n)d^2) for Exphormer layers (line 31) is unclear. The Exphormer paper's discussion is also missing. Specifically, why is there an $md^2$ term instead of $md$ (there are $m$ dot product between $d$-dimensional vectors)? Additionally, why does the $d^2$ term change to $d$ in the Spexphormer complexity (line 77)?

We briefly discussed this in lines 149-153, but will clarify.
$md^2$ is because of the line `E = self.E(edge_attr)` in `ExphormerAttention.forward`, in the file `Exphormer/graphgps/layer/Exphormer.py` from the Exphormer repo. This edge feature mapping is a $d \times d$ multiplication, because Exphormer is used on datasets with many types of varying edge features. In Spexphormer, we only have three possible values of edge features, for each type of edge; thus we can replace that mapping with an edge type embedding, reducing the complexity to $m d$.
For all the memory comparisons we have fixed this on the Exphormer as well. This is a very small change, but it drastically saves memory as usually $m \gg n$. 

> Typically (including Exphormer), the equation would be ...

Our attention formulation is same as the Exphormer. We will revise this for future versions of our model. However, we should clarify that $W_O$ is actually of size $d \times d$ (not $m \times d$) in both Exphormer and the originating paper. $W_O$ will be applied on the concatenation of the heads, to mix the heads together. In our case, this can be combined with the next feed-forward network following the attention mechanism (as common in Transformer architectures). The reason why Exphormer cannot do that is that they combine their model with an MPNN, and the feed-forward network part applies on the combined representations coming from the Transformer part and the MPNN. Since we remove the MPNN part, we don't have this problem, and representationally $W_O$ can be absorbed into the next layer.

Meta-review: This work introduces Spexphormer, a two-stage process designed to address the scalability issues of Graph Transformers on large datasets by reducing memory complexity. Building on prior work (Exphormer), the method first trains a narrow network on a fully augmented random graph to estimate attention scores, which are then used to create sparser interaction graphs. These sparser graphs are employed to train a larger network, improving scalability without sacrificing performance. Experiments demonstrate some of Spexphormer claims.

**Weaknesses**
- The work essentially bills itself as a smaller-memory footprint Exphormer. This was seen as too incremental by some reviewers.
- Once we add attention to the edges of the expander graph, it obviously not guaranteed to be an expander anymore. This quirk of the method should be made clear. The initial shallower GNN will benefit from the expander, but maybe not the attention module.
- The sampling and expander will make the embeddings positional, losing equivariance (which is a very common drawback of graph transformers).
- The experimental analysis on scalability focuses on memory reduction, with less emphasis on runtime performance. This limited scope weakened the overall evaluation.
- The work should have talked more about the challenges of alternative efficient attention implementations like FlashAttention. It is important for the community to understand **precisely** why sparse attention methods are incompatible with directly applying FlashAttention.

**Strengths**
- Scalability of graph models is an important topic. 
- Working in layers, simpler models reduce the workload of more complex models, is a good direction to follow in general. This approach, even though applied to a narrow scenario (improve the memory footprint of Exphormer), it may inspire others.
- Well-written and structured paper, with clear explanations of methodology and experimental setups.
- The rebuttal has improved the paper. The new results should be included in the final paper, if accepted.
Decision: Accept (poster)