SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations
Authors: Qitian Wu
Wentao Zhao
Chenxiao Yang
Hengrui Zhang
Fan Nie
Haitian Jiang
Yatao Bian
Junchi Yan
Venue: NeurIPS 2023 poster (2023)
Keywords: graph transformers
graph neural networks
graph representation learning
large graphs
efficiency
scalability

Abstract: Learning representations on large-sized graphs is a long-standing challenge due to the inter-dependence nature involved in massive data points. Transformers, as an emerging class of foundation encoders for graph-structured data, have shown promising performance on small graphs due to its global attention capable of capturing all-pair influence beyond neighboring nodes. Even so, existing approaches tend to inherit the spirit of Transformers in language and vision tasks, and embrace complicated models by stacking deep multi-head attentions. In this paper, we critically demonstrate that even using a one-layer attention can bring up surprisingly competitive performance across node property prediction benchmarks where node numbers range from thousand-level to billion-level. This encourages us to rethink the design philosophy for Transformers on large graphs, where the global attention is a computation overhead hindering the scalability. We frame the proposed scheme as Simplified Graph Transformers (SGFormer), which is empowered by a simple attention model that can efficiently propagate information among arbitrary nodes in one layer. SGFormer requires none of positional encodings, feature/graph pre-processing or augmented loss. Empirically, SGFormer successfully scales to the web-scale graph ogbn-papers100M and yields up to 141x inference acceleration over SOTA Transformers on medium-sized graphs. Beyond current results, we believe the proposed methodology alone enlightens a new technical path of independent interest for building Transformers on large graphs.

SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations
Qitian Wu', Wentao Zhao', Chenxiao Yang', Hengrui Zhang?, Fan Nie',
Haitian Jiang', Yatao Bian", Junchi Yan-
1 Dept. of Computer Science and Engineering & MoE Key Lab of AI, Shanghai Jiao Tong University 2 Dept. of Computer Science, University of Illinois Chicago 3 Courant Institute, New York University
Tencent AI Lab
{4cho740, permanent, chr26195 youluc2001, yanjunchi Jasunchhh@ajtt Ju edu. cn, hzhan55duic. edu, hatian. jiang@nyu. edu, yatao. bian@gmail.. com
Abstract
Learning representations on large-sized graphs is a long-standing challenge due to the inter-dependence nature involved massive data points. Transformers, as emerging class of foundation encoders for graph-structured data, have shown promising performance on small graphs due to its global attention capable of cap- turing all-pair influence beyond neighboring nodes. Even existing approaches tend to inherit the spirit of Transformers in language and vision tasks, and embrace complicated models by stacking deep multi-head attentions. In this paper, criti- cally demonstrate that even using a one-layer attention can bring up surprisingly competitive performance across node property prediction benchmarks where node numbers range from thousand-level to billion-level. This encourages us to rethink the design philosophy for Transformers large graphs, where the quadratic global attention is a computation overhead hindering the scalability. We frame the pro- posed scheme Simplified Graph Transformers (SGFormer), which is empowered by a simple attention model that can efficiently propagate information among arbitrary nodes at the minimal cost of one propagation layer and linear complexity w.r.t. node numbers. Moreover, SGFormer requires none of positional encodings, feature/graph pre-processing or extra loss. Empirically, SGFormer successfully scales to the web-scale graph gebnn-ppersstt 100M and yields up to 141x inference acceleration over SOTA Transformers on medium-sizer graphs. Beyond current results, we believe the proposed methodology alone enlightens a new technical path of independent interest for building Transformers on large graphs. The codes are publicly available at https: // /gggtuu.bb.... com/ qqi SttianwSSSFFrmmer.
htttpp:///ithtt
1 Introduction
Learning on large graphs that connect interdependent data points is a fundamental problem in machine learning, with diverse applications in social and natural sciences [45; 15; 48; 43; 14]. One key challenge is to obtain effective node representations, especially under limited computation budget (e.g., time and space), that can be efficiently utilized for various downstream tasks.
Recently, Transformers have emerged as popular class of foundation encoders for graph-structured data, by treating nodes in the graph as input tokens, and show highly competitive performance on
Cooresponding author. This work was partly supported by National Key Research and Development Program of China (2020AAA0107600), NSFC (62222607) and STCSM 125111001000,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

graph-level tasks [10; 66; 58; 63; 39] and node-level tasks [57; 54]. The global attention mechanism in Transformers [50] can capture implicit dependeepessscces among nodes that are not embodied by input graph structures, but could potentially make difference in data generation (e.g., the undetermined structures of proteins that lack known tertiary structures [37; 64]). This advantage provides Transformers with the desired expressivity and leads to superior performance over graph neural networks in mmall-graph--ee -baed applications [64; 3; 11; 31; 36].
A concerning trend in current architectures is their tendency to automatically adopt the design philosophy of Transformers used in vision and language tasks [8; 2: 9]. This involves stacking deep multi-heat attention layers, which results in large model sizes and a data-hungry nature. However, this design approach poses significant challenge for Transformers to scale large graphs
Due to the global all-pair attention mechanism, the time and space complexity of Transformers often scales quadratically with respect to the number of nodes, and the computation graph grows exponentially as the number of layers increases. Thereby, training deep Transformers for large graphs with node numbers in the millions can be extremely resource-intensive and may require delicate techniques for partitioning the inter-connected nodes into smaller mini-batches in order to mitigate computational overhead [57; 54; 35; 5].
In small-graph- each instance is graph and there are typically abundant labeled graph instances in dataset, large Transformers may have sufficient supervision for generalization. However, in large-grapy saaee--rap--aaase based tasks such as node-level prediction for protein functions [19], where there is usually only a single graph and each node is an instance, labeled nodes may be relatively limited. This exacerbates the vulnerability of large Transformers overfitting in such cases.
tasks such as graph-level prediction for molecular property [18], where
Our Contributions. This paper presents our initial attempt to reassess the need for deep atten- tions when learning representations large graphs. Critically, we demonstrate that single-layer single-head attention model can perform surprisingly competitive across twelve graph benchmarks, with node numbers ranging from thousands to billions. Our model, framed as Simplified Graph Transformer (SGFormer). is equipped with a simple global attention that scales linearly w.r.t. the number of nodes. Despite its simplicity, this model retains the necessary expressivity to learn all- all-pair interactions without the need for any approximation. Furthermore, SGFormer does not require any positional encodings, feature or graph rre-processing, extra loss functions, edge emheddings.
Experiments show that SGFormer achieves highly competitive performance in an extensive range of node property prediction datasets, which are used common benchmarks for model evaluation w.r.t. the fundamental challenge of representation learning on graphs, when compared to powerful GNNs and state-of-the-art graph Transformers. Furthermore, SGFormer achieves up to 37x/141x speedup in terms of training/inference time costs over scalable Transformers on medium-sizee graphs. Notably, SGFormer scale smoothly to the web-scale graph gebn-papers11 sippers10MM with O. nodes, two orders-of-nee of-ginitude larger than the largest demonstration of existing works on graph Transformers.
Additionally, as separate contribution, we provide insights into why the one-layer attention model can be a powerful learner for learning (node) representations on large graphs. Specifically, by connecting the Transformer layer to a well-established signal denoising problem with particular optimization objective, we demonstrate that a one-layer attention model can produce the same denoising effect multi-layer attentions. Furthermore, single attention layer can contribute to steepest descent on the optimization objective. These results suggest that a one-layer attention model is expressive enough to learn global information from all- all-pair interactions.
2 Preliminary and Related Work
We denote a graph as G= (V,E) where the node set V comprises N nodes, and the edge set E {u,, v) auv = 1} is defined by a symmetric (and usually sparse) adjacency matrix A [a.v]] NN. where ayo =
nodes u and v are connected, and otherwise. Each node has an input feature X, IR and a label Yu- The nodes in the graph are only partially labeled, forming node set denoted as Ver C V (wherein Ver < N). Learning representations on graphs aims to produce node embeddings 2, E IRd that are useful for downstream tasks. The size of the graph, as measured by the number of nodes N, can be arbitrarily large, usually ranging from thousands to billions.
2

---

Graph Neural Networks. The layer-wise updating rule for GNNs [44; 23] can be defined as recursively aggregating the embeddings of neighboring nodes to compute the node representation:
(k+1) (Z) (Z)
z((++1) Age (z) R(u))),
(I)
where ( denotes the embedding at the k-th layer, 1 denotes (parametric) feature transformation, and Agg is an aggregation function over the embeddings of nodes in R(u) which is the receptive field of node u determined by G. Common GNNs, such as GCN [23] and GAT [5]], along with their numerous successors, typically assume that R(u) is the set of first-order neighboring nodes in G. By stacking multiple layers (c.g., K) of the updating rule in (1), the model can integrate information from the local neighborhood into the representation. Because GNNs involve neighboring nodes in the computation graph, which exponentially increase w.r.t. K, training them on large graphs (e.g., with a million nodes) in full-batch manner can be challenging. To reduce the overhead, GNNs require subtle techniques like neighbor sampling [65], graph partition [7], or historical embeddings [12]. Some works adopt knowledge distillation for inference on sparser graphs [61; 67] to accelerate inference, and more recently, MLP architectures are used to replace GNNs to accelerate training [60; 17].
Graph Transformers. Beyond message passing within local neighborhood. Transformers have recently gained attention as powerful graph encoders [10; 66; 63; 34; 25; 58; 4; 20; 39; 22]. These models leverage global all-pair attention, which aggregates all node embeddings to update the representation of each node. Global attention can be seen as a generalization of GNNs' message passing to a densely connected graph where R(u) = V. and equips the model with the ability to capture implicit dependencies such as long-range interactions or unobserved potential links in the graph. However, the all-pair attention incurs ((N2) complexity and becomes a computation bottleneck that limits most Transformers to handling only small-sized graphs (with up to hundreds of nodes). For larger graphs, recent efforts have resorted to strategies such as sampling a small (relative to N) subset of nodes for attention computation [16] or using ego-graph features input tokens [68]. However, these strategies sacrifice the expressivity needed to capture all- interactions among arbitrary nodes. Another line of recent works design new attention mechanisms that can efficiently achieve all-pair message passing within linear complexity. One of the pioneering work [57] proposes kernelized Gumbel-Softmax message passing that utilizes random feature maps approximate the all-pair attention with linear complexity. Another work [54] leverages the principled graph diffusion equation and resorts to the non-local diffusion operator to derive linear attention network that models all-pair interactions without any approximation.
Another observation is that nearly all of the Transformer models mentioned above tend to stack deep multi-head attention layers, in line with the design of large models used in vision and language tasks [8; 2: 9]. However, this architecture presents challenges for scaling to industry-scale graphs, where N can reach billions. Moreover, the model can become vulnerable to overfitting when the number of labeled nodes |erl is much smaller than N. This is common issue in extremely large graphs where node labels are scarce [19].
3 Simplifying and Empowering Transformers on Large Graphs
In this section, we introduce our approach, which we refer to Simplified Graph Transformers (SGFormer). The key component of SGFormer is a simple global attention model that captures the implicit dependencies among nodes with linear complexity.
Input Layer We first use a neural layer to map input features X = |x_] to node embeddings in the latent space, i.c., ( = fi (X) where fi can be a shallow (e.g.. one-layer) MLP. The node
embeddings (0) E Nxd will be used for subsequent attention computation and propagation.
Simple Global Attention. The global interactions in our model are captured by an all-pair attention unit that computes pair-wise influence between arbitrary node pairs. Unlike other Transformers. which often require multiple attention layers for desired capacity, we found that a single-layer global attention is sufficient. This is because through lae-r propagation over a densely connected attention graph, the information of each node can be adaptively propagated to arbitrary nodes within the batch. Therefore, despite its simplicity, our model has sufficient expressivity to capture implicit dependencies among arbitrary node pairs while significantly reducing computational overhead. In
3

---

(mini-batch pertition)
SGFormer Model
Simple Glcbal Attendon
Output
Inpur Data
16
X
GNN
Figure 1: Illustration of the proposed model SGFormer and its data flow. The input graph data entails node features X and graph adjacency A. For large graphs, we need to use mini-batch sampling that randomly partitions the input graph into mini-batches with smaller sizes. Each mini-batch is composed of the features of the nodes within this mini-batch Xm and the local graph adjacency Am (one can also use neighbor sampling as an alternative). The mini-batch data (Xm: Am) (for large graphs) or the whole graph data (X, A) (for small graphs) will be fed into the SGFormer model that is implemented with one-layer global attention and a GNN network. The model outputs the node representations for final prediction.
specific, we adopt a linear attention function defined as follows:
Q
K
Q (z)
Q
K = fx(((()),
K
V = fz()
(2)
Q
1 Q((T1)) N
Z = 3D V Q( v) + - (11-8)Z())
D= diag
(3)
N
where Sq. fK, Jv are all shallow neural layers (e.g., a linear feed-forward layer in our implemen- tation), || denotes the Frohenius norm, 1 is an N-dimensional all-one column vector, the diag operation changes the N-dimensional column vector into a N x N diagonal matrix, and 3 is hhper--praaee parameter for residual link. In Eqn. 3, Z combines the all-pair attentive propagation over N nodes and the self-loop propagation. The former allows the model to capture the influence from other nodes, while the latter preserves the information of the centered nodes. The computation of Eqn. (3) can be achieved in (NN) time complexity, which is much more efficient than the Softmax attention in original Transformers [50] that requires O(N)). While the Softmax attention possesses provable expressivity [1], its quadratic complexity hinders the scalability for large graphs. Our adopted design reduces the quadratic complexity to (N) and in the meanwhile guarantee the expressivity for learning all-pair interactions. Therefore, it can successfully be applied for learning representations on graphs with a large number of nodes at the cost of moderate GPU memory.
Incorporation of Structural Information. For accommodating the prior information of the input graph G. existing models tend to use positional encodings
[39], edge regularization loss [57] or augmenting the Transformer layers with GNNs [58]. Here we resort to simple-yet-effective scheme that combines with the propagated embeddings by GNNs at the output layer:
Zo = (1 - a + (Z (0), A), Y
fooo).
where is weight hyper-parameter and the GN module can be simple GNN architecture (c.g.. GCN [23]) that possesses good scalability for large graphs. The output function fo maps the final representation Zo to prediction depending specific downstream tasks, and in our implementation fo is a linear feed-forward layer.
Complexity Analysis. The overall computational complexity of our model is O(N - E), where E E) as the GN module requires OEE). Due to the typical sparsity of graphs (i.e., E < N2), our model can scale linearly w.r.t. graph sizes. Furthermore, with only one-layer global attention and simple GNN architectures, our model is fairly lightweight, enabling efficient training and inference.
Scaling to Larger Graphs. For larger graphs that even GCN cannot be trained on using full-batch processing with single GPU, we can use the random mini-batch partitioning method utilized by [57; 54]. This incurs only negligible additional costs during training and allows the model to scale to arbitrarily large graphs. Moreover, due to the linear complexity of our all-pair attention mechanism, we can employ large batch sizes, which facilitate the model in capturing informative global interactions among nodes within each mini-batch. Our model is also compatible with advanced techniques such as neighbor sampling [65], graph clustering [7], and historical embeddings [12]. which we leave for future exploration along this orthogonal research direction. Fig. 1 presents the data flow of the proposed model.

---

Table 1: Comparison of (typical) graph Transformers w.r.t. required components (PE for positional embeddings, MA for multiple attention heads, AL for augmented training loss and EE for edge embeddings), all-pair expressivity and algorithmic complexity w.r.t node number N and edge number E' (often E < N²). The largest demonstration means the largest graph size used by the papers.
Model Components
All-pair Expressivity
Algorithmic Complexity
Largest
Model
PE
MA
AL
EE
Pre-processing
Training
Demo.
GraphTransfomer [10]
R
R
R
Yes
O(Na)
O(N2)
0.2K
Graphormer [63]
R
R
R
Yes
O(N7)
((
0.3K
GraphTrans [58]
Yes
O(N2)
0.3K
SAT [4]
Yes
O(N*)
O(N2)
EGT [20]
Yes
O(Na
O(N*)
0.5K
GraphGPS [39]
R
Yes
O(N")
O(N +
1.0K
Gophormer [68]
R
No
O smc))
20K
NodeFormer [57]
R
R
Yes
O(N E)
2.0M
DIFFormer [54]
Yes
O E)
1.6M
SGFormer (ours)
Yes
O(N
0.1B
4
Comparison with Existing Models
In this section, we provide a more in-depth discussion comparing our model with prior art and illuminating potential in wide application scenarios. Table presents a head-to-head comparison of current graph Transformers in terms of their architectures, expressivity, and scalability. Most existing Transformers have been developed and optimized for graph classífication tasks on small graphs, while some recent works have focused on Transformers for node classification, where the challenge of scalability arises due to large graph sizes.
Architectures. Regarding model architectures, some existing models incorporate edge/positional embeddings (e.g.. Laplacian decomposition features [10], degree centrality [63]. Jeisfeiler-Lehmanl
labeling [66]) utilize augmented training loss (e.g., edge regularization [20; 57]) to capture graph information. However, the positional embeddings require an additional pre-processing procedure with complexity of up to O(N*), which can be time- and memory-consumine for large graphs, while the augmented loss may complicate the optimization process. Moreover, existing models typically adopt a default design of stacking deep multi- attention layers for competitive performance. In contrast, SGFormer does not require any of positional embeddings, augmented loss or pre- pre-processing, and only uses single-layer, single-head global attention, making both efficient and lightweight.
Expressivity. There are some recently proposed graph Transformers for node classification [68; 5] that limit the attention computation to a subset of nodes, such as neighboring nodes or sampled nodes from the graph. This approach allows linear scaling w.r.t. graph sizes, but sacrifices the expressivity for learning all- all-pair interactions. In contrast, NodeFormer [57] and SGFormer maintain attention computation over all N nodes in each layer while still achieving O(N) complexity. However, unlike NodeFormer which relies on random features for approximation, SGFormer does not require any approximation stochastic components and is more stable during training.
Scalability. In terms of algorithmic complexity, most existing graph Transformers have (NN2) complexity due global all-pair attention, which is critical computational bottleneck that hinders their scalability even for medium-sized graphs with thousands of nodes. While neighbor sampling can serve as a plausible remedy, it often sacrifices performance due to the significantly reduced receptive field [35]. SGFormer scales linearly w.r.t. N and supports full-batch training on large graphs with up to 0. IM nodes. For further larger graphs, SGFormer is compatible with mini-batch training using large batch sizes, which allows the model to capture informative global information while having a negligible impact on performance. Notably, due to the linear complexity and simple architecture, SGFormer can scale to the web-scale graph rebn-papeers 100M (with 0. nodes) when trained on single GPU, two orders-of-men maggnniu larger than the largest demonstration NodeFormer [57] and DIFFormer [54].
5 Empirical Evaluation
We apply SGFormer to various datasets of node property prediction tasks, which are used as common benchmarks for evaluating the model's efficacy for learning effective representations and scalability to large graphs. In Sec. 5.1, we test SGFormer on medium-sized graphs (from 2K to 30K nodes) and compare it with an extensive set of expressive GNNs and Transformers. In See. 5.2, we scale SGFormer to large-sized graphs (from M. to O. nodes) where its superiority is demonstrated over
5

---

Table 2: Mean and standard deviation (with five independent runs using random initializations) of testing accuracy on medium-sizer node classification benchmarks. We annotate the node and edge number of each dataset and OOM indicates out-of-memory when training on GPU with 24GB
memory. We highlight the best model with purple and the runner-up with brown in each dataset.
Dataset
Cora
CiteSeer
PubMed
Actor
Squirrel
Chameleon
Deezer
nodes
2,708
3.327
19,717
7,600
2223
890
28,281
# edges
5,278
4,552
44,324
29,926
46,998
8,854
92,752
GCN
81.6
71.6 01.4
78.8 0.6
30.1 0.2
38.6 1.8
41.3 # 3.0
62.7 + 0.7
GAT
83.0
72.1 # 1.1
0.4
2.1 0.6
3912
61.7 0.8
SGC
8.2
71.9 0.1
0.1
39.3 0.9
3.3
62.3 0.4
JKNet
0.5
70.7 + 0.7
0.7
0.7
39.4 1.6
3.8
61.5
APPNP
0.5
71.8 0.5
0.2
31.3 1.5
3 1.9
38.4
6
IL,GNN
8.8
71.4 0.7
0.4
34,4 1.7
3
4.0 38.1
66.2
SIGN
0.3
0.8
0.5
36.5
1.0
2.5
41.7 +
66.3 0.3
CPGNN
0.4
71.6
0.7
34.5 0.7
38.9
40.8 + 2.0
65.8 0.3
GloGNN
0.4
0.6
7,,9
36,4
3
40.2
6 0.8
Graphormer
0OM
0OM
OOM
COM
COM
COM
OOM
GraphormeTssauur
75.8
65.6 0.6
OOM
OOM
40.9 2.5
41.9
OOM
Graphormetu
63.6 0,9
OOM
33,9 1.4 0.7
3..9
4.8
OOM
GraphTranssMan
8.9
0.7
OOM
41.0
42.8 3.3
OOM
Graph Trans
81.7 0.6
70.2 0.8
0.5
0.8
40.6
42.2
2.9
OOM
NodeFormer
82.2 82.2
72.5 1.1
79.9 + 1.0
36.9 1.0
38.5
34.7 + 4.1
SGFormer
72.6 0.8
80.3 0.6
1.1
2.2
4.9
67.1
scalable GNNs and Transformers. Later in Sec. 5.3 and 5.4, we compare the time/space efficiency and analyze the impact several key components in our model, respectively. More detailed descriptions for datasets and implementation are deferred to Appendix B and C, respectively.
5.1 Results on Medium-sized Graphs
Setup. We first evaluate the model on commonly used graph datasets, including three citation networks cora, citeseer and pubmed, where the graphs have high homophily ratios, and four heterophilic graphs actor, squirrel, chameleon and deezer- tend to have distinct labels. These graphs have 2K-30K nodes. For citation networks, we follow the semi-supervisee setting of [23] for data splits. For actor and deezer- europe, we use the random splits of the benchmarking setting in [32]. For squirrel and chameleon, we use the splits proposed by recent evaluation paper [38] that filters the overlapped nodes in the original datasets.
where neighboring nodes
Competitors. Given the moderate sizes of graphs where most of existing models can scale smoothly. we compare with multiple sets of competitors from various aspects. Basically, we adopt standard GNNs including GCN [23]. GAT [51] and SGC [52] as basclines. On top of this, we compare with advanced GNN models, including JKNet [59], APPNP [24], SIGN [40], H2GCN [72], CPGNN [71] and GloGNN [27]. In terms of Transformers, we mainly compare with the ttate-of-the-ae models designed for node classification NodeFormer [57]. Furthermore, we adapt two powerful Transformers tailored for graph classification, i.e., Graphormer [63] and GraphTrans [58], for comparison. In particular, since the original implementations of these models are of large sizes and are difficult to scale on all node classification datasets considered in this paper, we adopt their smaller versions for our experiments. We use GraphormeTςsALL (6 layers and 32 heads), Graphormer (3 layers and 8 heads) and GraphormetULrRAASMa (2 layers and I head). As for GraphTrans, we GraphTrans (3 layers and 4 heads) and TraphTransuurrssauL (2 layers and head).
Results. Table 2 reports the results of all the models. We found that SGFormer significantly outperforms three standard GNNs (GCN, GAT and SGC) by a large margin, with up to 25.9% impv. over GCN on actor, which suggests that our one-layer global attention model indeed effective despite its simplicity. Moreover, we observe that the relative improvements of SGFormer over three standard GNNs are overall more significant on heterophilic graphs actor, squirrel, chameleon and deezer. The possible reason is that in such cases the global attention could help to filter out spurious edges from neighboring nodes of different classes and accommodate dis-com cisnccnne yet informative nodes in the graph. Compared to other advanced GNNs and graph Transformers (particularly NodeFoormer), the performance of SGFormer is highly competitive and even superior with significant gains over the runner-ups in most cases. These results serve as concrete evidence for verifying the efficacy of SGFormer as powerful learner for node-level prediction. We also found that both Graphormer and GranhTrans suffer from serious over- wetr-fitiin, due their relatively complex

---

Table Testing results (ROC-AUC for ogbn proteins and Accuracy for other datasets) on large- sized node property prediction benchmarks. The training of NodeFormer on 9gbn-papers1000 cannot be finished within an acceptable time budget.
Method
ogbn-proteins
Amazon2m
pokec
ogbn-arxiv
Ngbn-papers100X.
nodes
132,534
2,449,029
1,632,803
169,343
I11,059,956 9,56
edges
39,561,252
61.859.140
30,622,564
1.166,243
1611,685,872
ML.P
72.04 0.48
63.46
60.15 0.03
0.23
47.24 + 0.31
GCN
72.51 0.35
83.90 0.10
62.31 + 1.13
71.74 0.29
00M
SGC
70.31
81.21
52.03 0.84
67.79
63.29 = 0.19
GCN-NSampler
73.51 1.31
0
68.50 0.77
62.04 = 0.27
GAT-NSampler
74.63 1.24
85.17 0.32
62.32
67.63 + 0.23
63.47 = 0.39
SIGN
0.44
80.98 0.31
68.01 0.25
70.28 +
65.11 = 0.14
NodeFormer
77.45 1.15
87.85
0.24
70.32 0.45
59.90 0.42
SGFormer
0.38
89.09 + 0.10
73.76 0.24
72.63 # 0.13
66.01 + 0.37
Table 4: Efficiency comparison of SGFormer and graph Transformer competitors w.r.t. training time (ms) per epoch, inference time (ms) and GPU memory (GB) costs on a Tesla T4. We use the small model versions of Graphormer and GraphTrans. The missing results are caused by out-of-memory
Cora
PubMed
Amazon2M
Method
Tr (ms)
Inf (ms)
Mem (GB)
Tr (ms)
Inf (ms)
Mem (GB)
Tr (ms)
Inf (ms)
Mem (GB)
Graphormer
563.5
537.1
5.0
GraphTrams
160.4
40.2
3.8
NodeFormer
68.5
30.2
1.2
321.4
135.5
5369.5 2481.4
1410.0
SGFormer
15.0
3.8
15.4
4.4
1.0
382.5
2.7
SGFormer
NodeFormer
SCFomer w/ Softmax
Training
GPU memory cost
12.5
Memory (GB)
Time (ms)
10.0
1000
5.0
60
2.5
2
10
nodes (10*)
nodes (10*)
Figure 2: Scalability test of training time per epoch and GPU memory usage w.r.t. graph sizes (a.k.a. node numbers). NodeFormer suffers out-of-memory when # nodes reaches more than 30K.
architectures and limited ratios of labeled nodes. In contrast, the simple and lightweight architecture of SGFormer leads to its better generalization ability given the limited supervision in these datasets.
5.2 Results on Large-sized Graphs
Setup. We further evaluate the model on several large- datasets where the numbers of nodes range from millions to billions. The citation network ogbn- ogbn-arxiv and the protein interaction network ogbn-proteins contain 0.16M and 0.13M nodes, respectively, and these two graphs have different edge sparsity. We use the public splits in OGB [19]. Furthermore, the item co-occurrence network Amazon2M and the social network pokec consist of 2.0M and 1.6M node, respectively, and the latter is heterophilic graph. We follow the splits used in the recent work [57] for Amazon2M and use random splits with the ratio 1:1:8 for pokec. The largest dataset we demonstrate is ogbn-papers the node number reaches O.IB and we also follow the public OGB splits.
where
Competitors. Due to the large graph sizes, most of the expressive GNNs and Transformers compared in Sec. 5.1 are hard to scale within acceptable computation budgets. Therefore, we compare with MLP, GCN and two scalable GNNs, SGC and SIGN, We also compare with GNNs using the neighbor sampling [65]:
and GAT-NSampler. Our main competitor is NodeFormer [57], the recently proposed scalable graph Transformer with all-pair attention.
Results. Table 3 presents the experimental results. We found that SGFormer yields consistently
superior results across five datasets, with significant performance improvements over GNN competi- tors. This suggests the effectiveness of the global attention that can lear implicit inter-dependencces among a large number nodes beyond input structures. Furthermore, SGFormer outperforms NodeFormer by a clear margin across all the cases, which demonstrates the superiority of SGFormer that uses simpler architecture and achieves hetter performance on large graphs. For the largest dataset agon-paperss 100M 10OM where prior Transformer models fail to demonstrate, SGFormer scales smoothly
7

---

AcsraeyyROC-AUC
Trinling
Core
Acter
ogen-proteiis
1070
Pool raay
layers
Figure 3: Testing scores and training time per epoch of SGFormer w.r.t. # attention layers. More results on more datasets are deferred Appendix D.
SGFommer w/ Softmax
SGF ooree w/o self self-loop
NodeFormer
Cora
Actor
og ogbn-proteins
40
Accurcy
ROC- AUG
a
2
10
10
layers
layers
# layers
Testing performance of NodeFormer, SGFormer w/o self-loop and SGFormer w/ Softmax w.r.t. the number of attention layers. The missing results are caused by out-of-memory.
Figure 4:
with decent efficiency and yields highly competitive results. Specifically, SGFormer reaches the testing accuracy of 66.0 with consumption of about 3.5 hours and 23.0 GB memory on a single GPU for training. This result provides strong evidence that shows the promising power of SGFormer on extremely large graphs, producing superior performance with limited computation budget.
5.3 Efficiency and Scalability
We next provide more quantitative comparisons w.r.t. the efficiency and scalability of SGFormer with the graph Transformer competitors Graphormer, GraphTrans, and NodeFormer.
Efficiency Comparison. Table 4 reports the training time per epoch, inference time and GPU memory costs on cora, pubmed and Amazon2M. Since the common practice for model training in these datasets use fixed number of training epochs, we report the training time per epoch here for comparing the training efficiency. We found that notably, SGFormer is orders-of-magnie competitors. Compared Graphormer and GraphTram that require quadratic complexity for global attention and are difficult for scaling to graphs with thousands of nodes, SGFormer significantly reduces the memory costs due to the simple global attention O(N) complexity. In terms time costs, SGFormer yields 38x/141x maining/inference speedup over Graphormer on cora, and 20x/30x trainingfinference speedup over NodeFormer on pubmed. This is mainly because Graphormer requires the compututation of quadratic global attention that is time- come-conumingg and NodeFormer additionally employs the augmented loss and Gumbel tricks. On the large graph Amazon2M, where NodeFormer and SGFormer both leverage mini-batch training. SGFormer 2x and 4x faster than NodeFormer in terms of training and inference, respectively.
faster than other
Scalability Test. We further test the model's scalability w.r.t. the numbers of nodes within one computation batch. We adopt the Amazon2M dataset and randomly sample a subset of nodes with the node number ranging from 10K to 100K. For fair comparison, all the models. Fig. 2, we can see that the time and memory costs of SGFormer both scale linearly w.r.t. graph sizes. When the node number goes up to 40K, the model (SGFormer w/ Softmax) that replaces our attention with the Softmax attention suffers out-of -o--o---moory and in contrast, SGFormer costs only 1.5GB memory.
use the same hidden size 256 for
5.4 Further Discussions
We proceed analyze the impact of model layers the testing performance and further discuss the performance variation of other models w.r.t. the number of attention layers. Due to space limit, we defer more results to Appendix D.
How does one-layer global attention perform compared to multi-layer attentions of Eqn. 5? Fig. presents the testing performance and training time per epoch of SGForrer when the layer number of global attention increases from to more. We found that using more layers does

---

not contribute to considerable performance boost and instead leads to performance drop on the heterophilic graph actor. Even worse, multi-layer attention requires more training time costs. Notably, using one-layer attention of SGFormer can consistently yield highly competitive performance as the multi-layer attention. These results verify the effectiveness of our one-layer attention that has desirable expressivity and superior efficiency. In Sec. 6 we will shed more insights into why the one-layer all-pair attention an expressive model.
How does one-layer global attention of other models perform compared to the multi-layer counterparts? Fig. 4 presents the performance of NodeFormer, SGFormer w/o self-loop (removing the self-loop propagation in Eqn. 5) and SGFormer w/ Softmax (replacing our attention by the Softmax attention), w.r.t. different numbers of attention layers in respective models. We found that using one-layer attention for these models can yield decent results in quite few cases, which suggests that for other implementations of global attention, using a single-layer model also has potential for competitive performance. In some cases, for instance, NodeFormer produces unsatisfactory results on ogbn- penn-proteinss with one layer. This is possibly because NodeFormer couples the global attention and local propagation in each layer, and using the one-layer model could sacrifice the efficacy of the latter. On top of all of these, we can see that it can be promising future direction for exploring effective shallow attention models that can work consistently and stably well. We also found when using deeper model depth, SGFormer w/o self-loop exhibits clear performance degradation and much worse than the results in Fig. 3, which suggests that the self-loop propagation in Eqn. can help to maintain the competitiveness of SGFormer with multi-layer attentions.
6 Theoretical Justifications
To resolve lingering opaqueness on the rationale of our methodology, we attempt to shed some insights on why the one-layer attention model can be expressive enough for learning desirable representations from global interactions. We mainly consider the feature propagation step of one Transformer layer:
layer
layer
layer
N
(k) = (1 - -) (1-1) + t 2
(h) 2
11-
(5)
Energy
amoothivuae woweeeeee gineeri
multi-layor model
(R) where Gue is the attention score between node u and v at the k-th layer and 0 < S is a weight. For example, in
the original Transformers [50], Casi is the Softmax-
(k)
model
attention score. In our model Eqn. 3, we correspondingly N+9. k. N N+E k., and Cav N+ k. for
layer
layer 2
layor
have (k)
(k)
4. k.
Can
Figure 5: Illustration of the theoreti- cal analysis showing the equivalence be- tween the multi-layer and one-layer at- tention models. The one-layer attention model can produce the same effect on the smoothness criteria and help to save potential redundancy.
# u. Our analysis is mainly based the interpretation of one Transformer layer as an optimization step for a principled graph signal denoising problem [47; 21; 13] with particular objective. The denoising problem defined over N nodes in system aims at smoothing the node features by adaptively absorbing the information from other nodes. The denoised features synthesize the initial information and the global information under the guidance of the given objective.
Theorem 1. For any given attention matrix ((k) = [cue I Eqn. 5 is equivalent to gradient descent operation with step size 2x for an optimization problem with the cost function:
min Z
Σ 1l - (k- 11-1) +
+
(1) 1l. -
(6)
where X is a trading weight parameter for the local smoothness and global smoothness criteria [69].
For analysis and comparing the one-layer and multi-layer attention models, we extend our model to have arbitrary K layers, where each layer comprises an attention network of Eqn. 3 with independent parameterization. and use the superscript A to index each layer.

---

Eqn. 6 can be seen as generalization of the Dirichlet energy [70] defined over a dense attention graph, which is also utilized as the optimization target in the energy energy-constrained graph diffusion framework for designing principled and scalable attention layers [54]. Specifically, the pair-wise attention score (k) reflects the proximity between nodes u and v, and the attention matrix C(k) enforces adaptive denoising effect at the k-th layer. Since C varies layer by layer, multi-layer attention models can be seen as a cascade of descent steps on layer-dependent denoising objectives. As we will show in the next result, the multi-layer model can be simplified as single-layer one, while the latter contributes to the same denoising effect.
Theorem 2. For any K-layer attention model (where K is arbitrary positive integer) with the layer-wise updating rule defined by Eqn. 5. there exists C* = [cuel NxN N such that one gradient
descent step for the optimization problem (from the initial embeddings ( [z (2
min Z
2 + Σ
Cuullzu Zo 27
can yield the output embeddings (k) = 12.0 I
(K)
1 of the K-layer model.
The above result indicates that for any multi-layer attention model, one can always find a single-layer attention model that behaves the same way aggregating the global information. Moreover, the multi-layer model optimizes different objectives each layer, which suggests potential redundancy compared to the one-layer model that pursues a fixed objective in one step. And, according to Theorem 1, the one-layer model contributes to steepest decent step this objective. We present an illustration of our theoretical results in Fig. 5.
Conclusions and Outlooks
This paper explores the potential of simple Transformer-style architectures for learning sarge-graph representations where the scalability challenge plays bottleneck. Through extensive experiments across diverse node property prediction benchmarks whose graph sizes range from thousands to bil- lions, we demonstrate that a one-layer attention model combined with a vanilla GCN can surprisingly produce highly competitive performance. The simple and lightweight architecture enables our model, dubbed as SGFormer, to scale smoothly to an extremely large graph with 0.1B nodes and yields 30x acceleration compared to ofate-of-the-art Transformers accompanying theoretical justification for our methodology. On top of our technical contributions, we believe the results in this paper could shed lights new promising direction for building powerful and scalable Transformers on large graphs, which is largely under-cxplored.
medium-sized graphs. We also provide
Future Works. One limitation of the present work lies in the tacit assumption that the training and testing data comes from the identical distribution. Though this assumption is commonly adopted for research on representation learning where the main focus is the expressiveness and represen- tation power of the models, in practical scenarios, testing data may come from previously unseen distributions, resulting in the challenge of nut-of-distribution learning. Promising future directions could be to explore the potential of graph Transformers in mut-of-distribution generalization tasks where distribution shifts exist [56; 62], and the capabilities of graph Transformers for detecting disto--distribution samples [53; 30J. We leave more studies along these under-explored, orthogonal areas as future works.
Furthermore, in this work, we follow the common practice and mainly focus on the benchmark settings for evaluating the model w.r.t. a fundamental challenge of learning representations on large graphs. While in principle Transformers can be applied for other graph- tasks and more broadly domain-specific applications, such as recommender systems [55], circuit designs [6] and combinatorial optimization [28; 29], these scenarios often require extra task-dependent designs. We thereby leave exploration along this orthogonal direction aiming to unlock the potential of graph Transformers for various specific applications as future works.
References
[1] Anson Bastos, Abhishek Nadgeri, Kuldeep Singh, Hiroki Kanezashi, Toyotaro Suzumura, and Isaiah Onando Mulang'. How expressive are transformers spectral domain for graphs? Trans. Mach. Learn. Res., 2022, 2022.
10

---

[2] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020.
[3] Lowik Chanussot, Abhishek Das, Siddharth Goyal, Thibaut Lavril, Muhammed Shuaibi, Mor- gane Riviere, Kevin Tran, Javier Heras-Domingo, Caleb Ho, Weihua Hu, Aini Palizhati, Anuroop Sriram, Brandon M. Wood, Junwoong Yoon, Devi Parikh, C. Lawrence Zitnick, and Zachary W. Ulissi. The open catalyst 2020 (OC20) dataset and community challenges. CoRR, abs/2010.09990 2020.
[4] Dexiong Chen, Leslie O' O'Bray, and Karsten M. Borgwardt. Structure-aware transformer for graph representation learning. International Conference on Machine Learning, 2022.
[5] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. NAGphormer: A tokenized graph transformer for node classification large graphs. CoRR, abs/2206. 04910, 2022.
[6] Ruoyu Cheng and Junchi Yan. On joint learning for solving placement and routing in chip design. Advances in Neural Information Processing Systems, 34:16508-160 16519, 2021.
[7] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 257-266, 2019.
[8] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1810.04805, 2018.
[9] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
[10] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. CoRR, abs/2012.09693 2020.
[11] Zhiwen Fan, Tianlong Chen, Peihao Wang, and Zhangyang Wang. Cadtransformer: Panoptic symbol spotting transformer for CAD drawings. In /EEE/CVF Conference Computer Vision and Puttern Recognition, pages 10976-10986, 2022.
[12] Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In International Conference on Machine Learning, pages 2294-3304 2021.
[13] Guoji Fu, Peilin Zhao, and Yatao Bian. p-Laplacian based graph neural networks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato. edi- tors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings Machine Learning Research, pages 6878 6917. PMLR, 17-23 Jul 2022.
[14] Chen Gao, Jinyu Chen, Si Liu, Luting Wang. Qiong Zhang, and Qi Wu. Room-and coom-and-objecr aware knowledge reasoning for remote embodied referring expression. In IEEE Conference Computer Vision and Pattern Recognition, pages 3064-3073, 2021.
[15] Dario Ghersi and Roberto Sanchez. Improving accuracy and efficiency of blind protein- ligand docking by focusing on predicted binding sites. Proteins: Structure, Function, and Bioinformatics, 74(2):417-424, 2009.
[16] William I.. Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. pages 1024-1034, 2017.

---

[17] Xiaotian Han, Tong Zhao, Yozen Liu, Xia Hu, and Neil Shah. Mipinit: simple gnn training acceleration with mlp initialization, International Conference on Learning Representations, 2023.
Embarrassingly
[18] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb- Isc: A large-scale challenge for machine learning on graphs. arXiv preprint arXiv:2103.09430, 2021.
[19] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, 2020.
[20] Md. Shamim Hussain, Mohammed J. Zaki, and Dharmashankar Subramanian. Global self- attention as replacement for graph convolution. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
[21] Vassilis Kalofolias. How to learn graph from smooth signals. In Artificial Intelligence and Statistics, pages 920-929. PMLR, 2016.
[22] Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. CoRR, abs/2207 2022.
[23] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR), 2017.
[24] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
[25] Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Pruden- cio Tossou. Rethinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems, pages
2021.
[26] Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection., 2016.
[27] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, 2022.
[28] Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang. Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong sructtre-hardnesss aware baseline. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023.
[29] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 2023.
[30] Zenan Li. Qitian Wu, Fan Nie, and Junchi Yan. Graphde: A generative framework for debiased learning and out-of-distribution detection on graphs. In NewrIPS, 2022.
[31] Yi-Lun Liao and Tess E. Smidt. Equiformer: Equivariant graph attention transformer for 3d atomistic graphs. In International Conference on Learning Representations, 2023.
[32] Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non-homophilous graphs. CoRR, abs/2104.01404, 2021.
[33] Julian J. McAuley, Rahul Pandey, and Jure Leskovee. Inferring networks of substitutable and complementary products. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785-794, 2015.
[34] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal, Graphit: Encoding graph structure in transformers. CoRR, 04.2200000667. 2021.
12

---

[35] Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. CoRR, abs/2202.08455. 2022.
[36] Erxue Min, Yu Rong. Tingyang Xu, Yatao Bian, Peilin Zhao, Junzhou Huang, Da Luo, Kangyi Lin, and Sophia Ananiadou. Masked transformer for neighhourhood-awwe click-through rate prediction. CoRR, abs/2201.13311 2022.
[37] R Nagarajan, Shandar Ahmad, and M Michael Gromiha. Novel approach for selecting the best predictor for identifying the binding sites in dna binding proteins. Nucleic acids research, 41(16):7606-7611 2013.
[38] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we re- ally making progress? International Conference on Learning Representations, 2023.
[39] Ladislav Rampásek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems, pages 5998-6008, 2022.
[40] Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein. and Federico Monti. SIGN: scalable inception graph neural networks. CoRR, abs/2004. 111990 2020.
[41] Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Complex Networks, 9(2), 2021.
[42] Benedek Rozemberczki and Rik Sarkar. Characteristic functions graphs: Birds of feather, from statistical descriptors to parametric models. In ACM International Conference on Informa- tion and Knowledge Management, pages 1325-1334, 2020.
[43] Alvaro
Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter W. Battaglia. Learning to simulate complex physics with graph networks. In International Conference on Machine Learning, pages 8459-8468, 2020.
[44] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-80, 2008.
[45] Peter Schmidtke and Xavier Barril. Understanding and predicting druggability. a high- throughput method for detection of drug binding sites. Journal of medicinal chemistry, 53(15):5858-588) 2010.
[46] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi- Rad. Collective classification network data. Mag., 29(3):93-106, 2008
[47] David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83 2013.
[48] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 807-816.
[49] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 807-816, 2009,
[50] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Informa- tion Processing Systems, pages
2017.
[51] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018
13

---

[52] Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Wein- berger. Simplifying graph convolutional networks. In International Conference on Machine Learning, pages 6861-6871, 2019.
[53] Qitian Wu, Yiting Chen, Chenxiao Yang, and Junchi Yan. Energy-based out-of-distribution detection for graph neural networks. In ICLR, 2023.
[54] Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scalable (graph) transformers induced by energy constrained diffusion. International Confer- ence on Learning Representations, 2023.
[55] Qitian Wu, Hengrui Zhang. Xiaofeng Gao, Peng He, Paul Weng, Han Gao, and Guihai Chen. Dual graph attention networks for deep latent representation of multifaceted social effects in recommender systems. In The World Wide Web Conference. pages 2091-2102 ACM, 2019.
[56] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. In ICLR, 2022.
[57] Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. In Advances in Neural Information Processing Systems, 2022.
[58] Zhanghao Wu, Paras Jain, Matthew A. Wright, Azalia Mirhoseini, Joseph E. Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. In Advances in Neural Information Processing Systems, 2021.
[59] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, pages $449-5458. 2018.
[60] Chenxiao Yang, Qitian Wu, Jiahua Wang, and Junchi Yan. Graph neural networks are inherently good generalizers: Insights by bridging gnns and mips. International Conference on Learning Representations, 2023.
[61] Chenxiao Yang, Qitian Wu, and Junchi Yan. Geometric knowledge distillation: Topology compression for graph neural networks. Advances Neural Information Processing Systems, 35:29761-29775, 2022.
[62] Nianzu Yang, Kaipeng Zeng, Qitian Wu, Xiaosong Jia, and Junchi Yan. Learning substructure invariance for ouloo-diistrbuutin molecular representations. In NeurlPS, 2022.
[63] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform bad for graph representation? In Advances in Neural Information Processing Systems, 2021.
[64] Qianmu Yuan, Sheng Chen, Jiahua Rao, Shuangjia Zheng, Huiying Zhao, and Yuedong Yang. Alphafold2-aware protein-dna binding site prediction using graph transformer. Briefings Bioin- form., 23(2), 2022.
[65] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020.
[66] Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. CoRR, abs/2001.05 140, 2020.
[67] Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mips new tricks via distillation. International Conference Learning Representations, 2022.
[68] Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yanfang Ye. Gophormer: Ego-graph transformer for node classification. CoRR, abs/21 10094 2021.
14

---

[69] Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency, In Advances in Neural Information Processing Systems, pages 321-328, 2004.
[70] Dengyong Zhou and Bernhard Schölkopf. Regularization on discrete spaces. In Puttern Recognition, 27th DAGM Symposium, volume 3663. pages 361-368. Springer, 2005.
[71] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In AAAI Conference Artificial Intelligence, 2021.
[72] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, 2020.
15

---

A Proof for Technical Results
A.1 Proof for Theorem
Theorem 1. For given attention matrix C(A) = [can NNN, Eqn. 5 is equivalent to gradient
descent with step size 2X for an optimization problem with the cost function:
min Z
Σ 1z
11
+
(0 20
1
(8)
24,01
where À is trading weight for the local smoothness and global smoothness criteria [69].
Proof. We denote the cost function at the k-th layer as
E(Z; (H=
Σ Zzz
( Zu. 20112.
(9)
The gradient of (k-1) w.r.t. Zu be computed by
( ((--11)
2(zu- zu
(k-1)) + 2A
Σ
(k) (Z,, 2.).
(10)
Oz.
The gradient descent with step size layer is
that minimizes the cost function E'Z; ()k at the current
2x
ØE(Z: ()
(1)
z T
(k-1)
Oz.
Z= 1)
(k-1) 1)= - 2X
(2 (k-1)
(k-1))
- 7
1 Σ
c (2!
(b-1) 2. 2(6-1))
zu
2X
(II)
= =(1 -T-) T) Σ
(k) Ze
(R- Σ
11=
cu 2
(1 (
uu (k-1)
(2))
The last step is due to the normalization of the attention scores, i.e. E, (l)) Eqn. 18 is the updating equation of the k-th layer of Transformers, i.e., Eqn. 5.
A.2 Proof for Theorem 2
Theorem 2. For any K-layer attention model (where K is an arbitrary positive integer) with the layer-wise updating rule defined by Eqn. 5, there exists C [cuelNxN such that one gradient descent step for the optimization problem (from the initial embeddings Z
[zu 1
lu=))
min 2
Σ
2
(0)
Σ
Giullzn Zo 12.
(12)
can yield the output embeddings (K) = [Z
(K)
u=1 of the K-layer model.
Proof. Assume the K K-layer model with the layer-wise updating rule defined by Eqn. 5 yields
sequence of attention matrices and node embeddings (11), 2 (22) ( ,.. ,,,,,,,,,, C(K), (K), We define propagation matrix (();
0
1
l
0
(K)
(M) = (1 0:)
+
a
21
C92
(1 - (1-x)] [ (.()) (13)
(k)
(k)
CNI
N
16

---

Then Eqn. 5 can be equivalently written as
z (k) -(()
(14)
By stacking K layers of propagation, we can denote the output embeddings as
Z pl = p = PP() (1)) P'
(15)
We next conclude the proof by construction. Defining C* + (P-
T²) II) where in specific,
C11
di
iN
Pi1
Pia
PiN
0
0
21
22
2N
1
P21
P22
P2N
0
C
T
CN
CN2
CNN-
Liv1
PN2
Piv
(16)
We show that solving the denoising problem with gradient step size 2x w.r.t. the objective
min
Z
10)12
Σ
Gillzz 2 12
(17)
Z
06.0
will induce the output embeddings (K), by noticing that
T"
ÖE Z (
2X
Oz.
(=
=2 (0)
(2
2(0)
2 2X
Cup (z)
-z!")
=(1 - T*)
(0)
+ Σ
(0
(18)
=(1 T 2 (0) + Σ
Cup 2
=(1 T" 20)2(0 (0) + (foPice
Pice +1
1
(0)
+ Σ
Punz 20
T
T
Σ Pun 20)
And, have E. Pun 20 (K)
since by definition Z (0
Dataset Information
Table 5: Information for node property prediction datasets.
Datasef
Property
Nodes Tasks
Edges
Feats
Classes
Cora
homophilous
2,708
5,429
1,433
CiteSeer
homophilous
3,327
3,703
PubMed
homophilous
19,717
44,324
500
3
Actor
heterophilic
7,600
29,926
931
5
Squirrel
heterophilic
5,201
216.933
2,089
5
Chameleon
heterophilic
2,277
36,101
2.325
5
Deezer
heterophilic
28,281
92,752
31,241
2
ogbn-proteins
multi-task
112
132.534
39,561.252
2
Amazon2M
long-range dependence
2,449,029
61,859,140
100
47
pokec
heterophilic
1,632,803
30,622.564
65
2
ogbn-arxiv
homophilous
169,343
1,166,243
128
40
ogbn-papers100M
homophilous
111,059.956
1.615.685.872
128
172
Our experiments are based on real-world datasets which are publicly available with open access. The information of these datasets is presented in Table 5.
17

---

cora, citeseer and pubmed [46] are three networks that contain citations, with nodes representing documents and edges representing citation links. The features of the nodes are represented as bag-of-words, capturing the content of the documents. The goal is to predict the academic topic of each paper. We follow the semi-supervised settings in [23], using randomly sampled 20 instances per class as training set, 500 instances as validation set, and 1,000 instances as testing set.
actor is the actor-only induced subgraph of the film-directoractor--iiii network [49]. In this dataset, each node corresponds to actor, and the edges between nodes signify their co-occurrence on the same Wikipedia page. The node features are comprised of keywords extracted from the respective actors' Wikipedia pages. The goal is to classify the nodes into five categories based on the content of the actors' Wikipedia pages. This dataset exhibits a relatively low homophily ratio and belongs
heterophilic graph.
squirrel and chameleon are two page-page networks that focus on on specific topics in Wikipedia [41]. In these datasets, the nodes represent web pages, and the edges denote mutual links between the pages. The node features are composed of selection of informative nouns extracted from the corresponding Wikipedia pages. The goal is to categorize the nodes into five distinct groups based on the average monthly traffic received by each web page. Furthermore, these datasets are recognized as heterophilic graphs, indicating the presence of connections between nodes with distinct labels. A recent paper [38] indicates that the original split of these datasets introduces overlapping nodes between training and testing, and propose a new data split that filters out the overlapping nodes. We use its provided split for evaluation.
deezer- is a user-user network of European members of the music streaming service Deezer [42]. In this network, the nodes represent users, while the edges signify mutual friendships between these users. The node features are based on the artists that the streamers have liked. The goal is to classify the gender of the users. We follow the benchmark setting in [32] and use random 50% train/valid/test split.
ogbn-proteins consists of graph where nodes correspond to proteins and edges indicate various biologically significant associations between proteins, categorized by their types (based on species). Each edge is accompanied by 8-dimensional features, with each di- mension representing the approximate confidence level of specific association type and ranging from 0 to The proteins in the dataset originate from 8 different species. The goal is to predict the presence or absence of 112 protein functions using a multi- binary classification approach. We use the public OGB split [19].
ogbn- is a citation network among all Computer Science (CS) Arxiv papers, as described by [19]. In this network, each node corresponds to an Arxiv paper, and the edges indicate the citations between papers. Each paper associated with 128-dimensional feature vector, obtained by averaging the word embeddings of its title and abstract. The word embeddings are generated using the WORD2VEC model. The objective is to predict the subject areas of Arxiv CS papers, specifically targeting 40 distinct subject areas. We adopt the split of [19], which involves training the model on papers published until 2017, validating on those published in 2018, and testing on papers published from 2019 onwards.
Amazon2M is derived from the Amazon Co-Purchasing network [33]. In this dataset, each node represents a product, and the presence of a graph link between two products indicates that they are frequently purchased together. The node features are generated by extracting bag-of-word features from the product descriptions. The labels assigned to the products are based on the top-level categories they belong to. We follow the recent work [57] using random split with the ratio 50%/25%//25%.
pokec [26] is a large-scale social network dataset that encompasses various features, in- cluding profile information like geographical region, registration time, and age. The goal is to predict the gender of users based on these features. For data split, we randomly divide the nodes into training, validation, and testing sets, with ratios of 10%, 10%, and 80%, respectively.
ogbn-papers 100M is gigantic web-scale graph that consists of 111 million papers as nodes. The difference of this dataset from others is that not all nodes are labeled and the labeled ratio is relatively low. The labeled portion comprises approximately 1.5 million
18

---

ARXIV papers, each of which is labeled with one subject area. The goal is to classify the paper into 172 ARXIV subject areas. We also follow the public split by OGB [19]. This dataset is nearly the largest public graph benchmark.
C Implementation Details
In this section, we provide more details regarding the model implementation, including model architectures, hyper-paramen settings and training details, facilitate the reproducibility.
C.1 Model Architectures
Our model is comprised of four modules: input layer, global attention, GNN model, and output layer. We present the details for each of them as follows.
The input layer a one-layer MLP with non-linear activation that transforms the input features E R NxD to the node embeddings in the latent space 7 E Nx
The global attention computes the all-pair influence among N nodes through the attention mechanism as described in Eqn. 3. Specifically, it feeds the initial embeddings ( Nxx into one-layer attention network and outputs the updated embeddings Z RR that absorbs the global information from other nodes.
The GNN network GN is instantiated as a graph convolution network which takes the input graph A and the initial embeddings ( e Rx as input and outputs the updated embeddings for each node. The latter is then linearly added with the output embeddings of the global attention, i.c., Zo = - a + aGN(Z (0) A). as the final representation for each node.
The output layer a feed-forward layer for prediction, which maps the node representations Zo E R into the predicted labels Y. The prediction Y will be used for computing the standard loss function of the form Σ,, ((uu, Mu), where ((-,-) can be cross-entropy for classification tasks or mean square error for regression tasks.
C.2
Training Details
We use different training schemes for graph datasets of different scales. For relatively small graphs (e.g., from 1K to O.IM nodes), we use full-graph training: for larger graphs that cannot be trained in a single GPU, we consider mini-batch training. The training details are introduced below.
Full-Graph Training. For the datasets presented in Table and ogbn- agbn-arxiv, we use the full- graph training. In specific, feed the whole graph into the model and compute the all-pain attention among all the nodes and predict their labels for loss computation. For inference, similarly, we use the whole graph as input and compute the metric based on the prediction for the validation/testing nodes.
Mini-Batch Training. For datasets (except aebnnaaxiin presented Table 3, due the large graph sizes, we consider the mini- training scheme used in [57]. Specifically, at the beginning of each training epoch, we randomly shuffle the nodes and partition the nodes into mini-batches with the size B. Then in each iteration, we feed one mini-batch (the input graph among these B nodes are directly extracted by the subgraph of the original graph) into the model for loss computation on the training nodes within this mini-batch. Then for inference on ogbn-pze proteins, Amazon2M and pokec (with MM to IM nodes), following the pipeline in [19] for evaluation, we can feed the whole graph into the model using CPU, which computes the all-pair attention among all the nodes in the ogbn-papers moderate memory during inference, papers 1 100M that cannot be fed as whole into the CPU with adopt the mini-batch partition strategy used in training to reduce the overhead. Since our model allows large batch sizes, we found the mini-batch partition can yield decent performance. In specific, we set the batch size 10K, M. O. and 0.4M for ogbn-proteins, Amazon2M, pokec and ogbn-pon -ooo--apprs100M. respectively.
dataset. For the gigantic graph ogbn-
Evaluation Protocol. We follow the common practice for node classification tasks and set fixed number of training epochs: 300 for medium-sized graphs, 1000 for large-sized graphs, and 50 for the extremely large graph Sooon-paprss000 The testing accuracy achieved by the model that reports
19

---

the highest result on the validation set is used for evaluation. We run each experiment with five independent trials using different initializations, and report the mean and variance of the metrics.
C.3 Hyper-parametees
We use the model performance on the validation set for hyper-parameter settings of all models including the competitors. Unless otherwise stated, the hyper-parameters selected using grid search with the searching space:
learning rate within {0.001, 0.0,, 0.1};
weight decay within {le - 5, le 4,5e - 4, le - 3, le -2]
hidden size within {32, 64, 128, 256);
dropout ratio within {0, 0.2, 0.3, 0.5);
number of layers within 21,
The searching space for other hyper- parameters that differ in each model is as follows:
GAT: head number {4, 8, 16).
SGC: hop number (1,
APPNP: (021, 0.5, 0.9).
JKNet: jumping knowledge type E (max, concatenation).
CPGNN: pretraining epochs E {100, 200.
SIGN: hop number E 21,
GloGNN: E 00, 1), 31 E 10). B2 E {01, 100, 1000), y [0,0.9]. norm layers E (1,2,3), K
E [1.
Graphormer: embedding dimension {64, 128, 256, 512].
GraphTrans: The dimension GCN (16, 32, 64, 128).
attentive module {64, 128, 256}, the dimension of the
NodeFormer: rb_ rb_order E 2,,2,3 hidden channels E {16, 32, 64, 128). edge regularization weight [0, 1), head number E {1, 3.4).
SGFormer: number of global attention layers is fixed as 1, number of GCN layers {1,2, 3). weight a within {0.5, 0.8).
D More Empirical Results
In this section, supplement more experimental results further study what patterns the global attention learn from data. We visualize the attention matrices given by SGFormer on different datasets, and the results are shown in Fig. We found that overall, the attention graphs are quite different from the input graphs, which implies that the global attention mechanism indeed captures certain informative patterns from data that are helpful for downstream prediction. Furthermore, since our model uses one-layer attention, the attention scores estimated by the model can be used for interpreting the influence among samples. For instance, as shown by the results, there are some sharp lines in the heat map which corresponds to the nodes that are recognized important 'information source' by the model and allocated with large attention weights. These nodes are akin to some hubs in the network that exert much influence other nodes.
20

---

(a) cora
(b) citeseer
(c) pubmed
(d) actor
ogbn-proteins
Amazon2M
Figure 6: Visualization of the attention weights produced by SGFormer.
21


Reviews:
[{"review_id": "xVds0Ni5Th", "reviewer": "Reviewer_J3Wh", "summary": "SGFormer adapts the transformer to large graphs by replacing the usual quadratic self-attention mechanism with a convex combination of linear attention and an arbitrary Graph Neural Network (GNN). The benchmark using node prediction tasks from Open Graph Benchmark (OGB) and achieve SOTA results. Moreover, the method is fast and scales to large graphs. They provide some theoretical justification why their one layer method can be as good as multiple layers.", "questions": "I would be curious if there is any way to figure out the contribution of the GNN and linear attention? Is there a way to get some intuition like looking at attention scores?\n\nMaybe some clustering of the embedding space could be interesting.", "limitations": "The paper only focuses on node prediction tasks.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written. Although dense, it provides a good summary of related works and experiments and methodology are clear.\n\nResults are very strong in terms of model quality and performance.\n\nThe simplicity of the method is appreciated.", "weaknesses": "There seems to be a lot of hyperparameters in the attention mechanism like \\alpha and \\beta that were not ablated? Also the structure of the GNN may matter a lot?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive comments and constructive suggestions that can help to further improve our work. \n\n> **(W1): Discussions of $\\alpha$, $\\beta$ and importance of graphs**\n\nIn Table 6 (in the appendix), we provide ablation studies for different values of $\\alpha$ (the weight of GNN). The results show that the GNN module is particularly important for homophily graphs (like Cora) and less important for heterophily graphs (like Actor). Since the GNN module can utilize the input graph information complementary to the all-pair global attention, its importance would depend on the informativeness of graph structures in different cases.\n\nBesides, we run some new experiments on CiteSeer and Chameleon with different settings of $\\beta$, and report the results in Table 3 in the uploaded PDF. We found the model is overall insensitive to $\\beta$ within a proper range.\n\n> **(Q1): Visualization of attention and node embeddings**\n\nWe originally present some visualization for the attention scores in Fig. 16 in the appendix. We found that the attention matrices (that have some dominant lines) tend to have different patterns with the graph adjacency matrices (that are sparse and scattered). This suggests the attention indeed learns some useful information from data beyond the input graph.\n\nAlso, following the advice, we add some visualization of the node embeddings in Fig 1 in the uploaded PDF. We found the attentive graph (by filtering the edges with attention weights larger than a threshold) is significantly different from the observed graph. Besides, the global attention of SGFormer pushes the node embeddings to have smaller intra-class distance than those of GCN.\n\nPlease let us know if you had further questions."}, {"review_id": "6inX8v1mGR", "reviewer": "Reviewer_9PQr", "summary": "This paper proposes Simplified Graph Transformers (SGFormer) that uses a one-layer attention to achieve competitive performance in node property prediction benchmarks.", "questions": "1. Is the theorems still applicable when subnets exist between two global attention layers?\n2. Why do you normalize the query and key in eq(2) with Frobenius norm?", "limitations": "Please refer to the weakness section", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea and the design of the simple global attention is novel.\n2. The proposed SGFormer is efficient and scalable.", "weaknesses": "The analysis in section 6 ignores possible sub-nets (e.g. FFN with non-linearity in the original transformer architecture) between two global attention layers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable comments and insightful questions which can allow us to further illuminate the applicability of the theory.\n\n> **(Q1): Applicability of the theory when subnets exist**\n\nThe theorems can be applied to the cases with FFN and non-linearity by some extension. For Theorem 1, the cost function will change after involving layer-wise FFN, and the non-linear activation can be seen as a proximal operator for gradient descent. In specific, the updating of one Transformer layer with the FFN (denoted as $h^{(k)}$) and non-linear activation (denoted as $\\sigma$) can be written as\n$$\n\\mathbf z_u^{(k)} = \\sigma\\left ( (1-\\tau) h^{(k)} ( \\mathbf z_u^{(k-1)})  + \\tau \\sum_{v=1}^N c_{uv}^{(k)} h^{(k)} ( \\mathbf z_v^{(k-1)} ) \\right ).\n$$\nWe can prove the above updating equation is essentially a proximal gradient descent step for optimizing the new cost function\n\n$$\n\\min_{\\mathbf Z} \\sum_{u} ||\\mathbf z_u - h^{(k)}(\\mathbf z_u^{(k-1)}) ||^2_2 + \\lambda \\sum_{u,v} c_{uv}^{(k)} ||\\mathbf z_u - \\mathbf z_v ||_2^2\n$$\n\nThe proof can re-use that of Theorem 1 by starting with computing the gradient of the objective. Then there are two differences. First, in Eqn. 11, we need to evaluate the gradient at $\\mathbf Z = h^{(k)}(\\mathbf Z^{(k-1)})$ instead of $\\mathbf Z = \\mathbf Z^{(k-1)}$. Second, after the gradient descent, we can add a proximal operator to map the updated result into a feasible region:\n\n$$\n\\mathbf z_u^{(k)} = Prox_{\\Omega} \\left ( (1-\\tau) h^{(k)} ( \\mathbf z_u^{(k-1)})  + \\tau \\sum_{v=1}^N c_{uv}^{(k)} h^{(k)} ( \\mathbf z_v^{(k-1)} )   \\right ),\n$$\n\nwhere $Prox_{\\Omega} (z) = \\arg\\min_{x\\in \\Omega} d(x, z) $, $\\Omega$ defines a feasible region and $d$ denotes the distance (e.g., l2). This gives rise to a proximal gradient descent which still guarantees a strict minimization for the objective, and the above equation coincides with the one-layer updating equation shown at the beginning. In particular, if one uses ReLU activation, the proximal operator will be $\\mbox{Prox}_{\\Omega} (z) = \\max(0, z)$.\n \nFor Theorem 2, if one only considers FFN without non-linearity, then the proof can be trivially extended to obtain the same result. In specific, for Eqn. 15, one can alter the order of the weight matrices and propagation matrices:\n$$\n\\mathbf Z^{(K)} = \\mathbf P^{(K)} \\mathbf W^{(K)} \\cdots \\mathbf P^{(1)} \\mathbf W^{(1)} \\mathbf Z^{(0)} = \\mathbf P^{(K)} \\cdots \\mathbf P^{(1)} \\mathbf W^{(K)} \\cdots \\mathbf W^{(1)} \\mathbf Z^{(0)} = \\mathbf P^* \\mathbf W^* \\mathbf Z^{(0)}\n$$ \n\nIn this way, we can similarly construct a propagation matrix $\\mathbf P^*$ that yields the same result as the multi-layer model. Furthermore, if we consider the FFN with non-linear activation, the proof cannot be directly adapted, though the result still loosely holds by considering the FFN as a two-layer MLP with universal approximation power. In this situation, the one-layer attention model can approximate any function mapping from $\\mathbf Z^{(0)}$ to $\\mathbf Z^{(K)}$ yielded by the multi-layer attentive propagation.\n\n> **(Q2): Why use normalization with Frobenius norm**\n\nThe normalization can restrict the magnitude of query and key vectors and avoid the explosion of the attention scores. In practice, we found the normalization works smoothly across different datasets and can yield stably good results.\n\nPlease let us know if you had further questions."}, {"review_id": "88Ngz07FHy", "reviewer": "Reviewer_moxf", "summary": "The paper presents a novel approach called Simplified Graph Transformers (SGFormer) for large-graph representations using Transformers. SGFormer achieves competitive performance with just one-layer attention, eliminating the need for positional encodings, pre-processing, and augmented loss. The paper provides theoretical justification for the methodology and suggests potential future directions for building powerful and scalable Transformers on large graphs.", "questions": "- I'm curious why this simple design of message passing works. Without attention or relative distance encoding, how could the model learn to down-weight nodes that are far from the center node?", "limitations": "The authors discussed some limitations. I don't see any potential negative social impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- SGFormer simplifies the design philosophy for Transformers on large graphs, making it highly efficient and scalable.\n- The paper provides theoretical justification for the methodology, which can help in understanding and improving the approach.\n- The authors experimented with ample datasets. The empirical results look promising.\n- The writing is clan and easy to follow.", "weaknesses": "- The paper mainly focuses on node property prediction tasks, and it is unclear how well SGFormer performs on other graph-based tasks such as link prediction, node clustering, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and we are glad that you liked our approach.\n\n\n> **(Q1): Why simple attention works? How the model learns to down-weight far-away nodes?**\n\nThank you for proposing this insightful inquiry. The principle of our model is that the one-layer all-pair message passing can allow information flows among arbitrary node pairs and enable the model to adaptively leverage the global information. To further support this conjecture, we provide theoretical discussions in Section 6 from the signal denoising perspective. \n\nThe model is not necessarily supposed to down-weight far-away nodes, depending on specific datasets with different properties. For instance, for heterophilic graphs or graphs with long-range dependence, the distant nodes could be informative and thus could be assigned with large attention scores. On the contrary, the case can be different for homophilic graphs. Generally speaking, we do not enforce any constraint on the attention learning and instead let the model flexibly learn useful inter-dependencies in a fully data-driven way. As further investigation, we provide more visualization for the node embeddings and graph/attention structures in Fig 1 in the uploaded PDF. We found the attentive graph is significantly different from the observed graph and the global attention can help to shorten the intra-class distance for better classification.\n\n\n> **(W1): Other graph-based tasks**\n\nWe are happy to supplement more discussions on the potential applicability of SGFormer. As illustrated in Section 7, since our paper focuses on exploring a simple architecture for the fundamental challenge large-graph representations, we follow common practice using node property prediction benchmarks for evaluation. We use graphs with different sizes to broaden the scopes of our experiments, which suits the evaluation w.r.t. the model's scalability, and the results show the superiority of SGFormer on graphs with #node ranging from thousands to billions. This suggests the model can potentially be applied to other tasks defined over graph data with these scales, e.g., link prediction and node clustering. Having said that these tasks as well as more broadly domain-specific applications often require extra task-dependent designs which can be equally incorporated with our model as well as the competitors. We thereby leave exploration along this orthogonal direction as future works. \n\nPlease let us know if you had further questions."}, {"review_id": "OsvBWyq6El", "reviewer": "Reviewer_bWXq", "summary": "Paper proposes a linear attention mechanism in the transformers for graph data. The attention becomes linear by eliminating the softmax in the dot product attention and multiplying K (transposed) and V matrices first followed by multiplication with Q matrix. The Q, K matrices are normalized by their respective frobenius norms to prevent explosion in the dot products. Authors further propose using a single attention layer instead of multiple layers. This they claim is sufficient over multiple layers from a signal denoising perspective. Experimental results demonstrate comparable results with baselines. The linear attention mechanism helps in reducing training compared to baselines.", "questions": "1) In the large datasets it appears that the optimal baseline results have been omitted. For example in the ogbn-papers dataset there are efficient transformers (https://arxiv.org/abs/2009.03509) that achieve better results than reported in this paper. Also on the same dataset SIGN method reports best result of 69.84 but lesser value is reported. Since the proposed method is not a pure transformer but a mix of GNN and transformer have the authors tried inducing the proposed linear attention in GraphGPS framework for the large datasets?\n2) While the method claims to not be using PEs, the authors induce representations learnt from a GNN which indirectly acts as a PE. This is similar to the framework of GraphGPS and the claim doesn’t seem to hold. I would expect further clarification on why the GNN is not a PE and whether the proposed method can work independent of the GNN (which does not seem to be the case from the ablations in appendix).\n3) While it is understandable that eliminating softmax helps gaining efficiency, are there any drawbacks? For example is the attention now more dense or some attention matrix values cannot be achieved or are there some other issues? The authors show an ablation that results with softmax are poor but this is in the entire architecture including the GNN etc. I would suggest performing an isolated study on the importance of and impact of eliminating softmax.\n4) Considering the method uses a single layer of attention, is it expressive enough to learn complex functions and permit pretraining? For example if the authors would pretrain the existing method on a large scale dataset and finetune on a  smaller dataset would it generalize as graphormer and related methods have shown?\n5) In theorem 1 the authors mention that equation 5 is the gradient descent solution to the low pass smoothing objective. But what if the objective is to learn some other function that does not have a low frequency characteristic? Would multiple attention heads still not help in that case?", "limitations": "The limitations of the method have been addressed in the paper.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "1) The model is shown to be efficient compared to the standard scaled dot product attention which enables scaling to graphs with millions of nodes.\n2) The results are comparable with baselines", "weaknesses": "1) Considering that the essence of the method lies in the linear attention which is obtained by eliminating nonlinearity and using the associative property of matrix multiplication, the novelty is limited. Further analysis needs to be done on what is the benefit/deterioration due to the elimination of softmax in isolation.\n2) The gains for the small datasets are marginal, in some cases within deviation. In the large datasets too it appears that the optimal baseline results have been omitted. For example in the ogbn-papers dataset there are efficient transformers (https://arxiv.org/abs/2009.03509) that achieve better results than reported in this paper. Also on the same dataset SIGN method reports best result of 69.84 but lesser value is reported. Since the proposed method is not a pure transformer but a mix of GNN and transformer I would also suggest trying GraphGPS on the same GNN and another efficient transformer on these large datasets as a fair baseline.\n3) While the method claims to not be using PEs, the authors induce representations learnt from a GNN which indirectly acts as a PE. This is similar to the framework of GraphGPS and the claim doesn’t seem to hold.\n4) In continuation to the above point, the results without GNN are very poor and so it seems that it is not the transformer alone that gives the gain but the combination with the GNN. Thus the results may not just be from the single layer linear attention as claimed and the claim should be modified in accordance with the experimental evidence.\n5) The model with linear attention also seems to be having problems scaling to large graphs and the authors resort to sampling techniques from Nodeformer for the same. Since efficiency is the main proposed contribution of the paper it is expected in principle to be integrated in the method rather than induced externally.\n\nMissing Citations:\n1) https://proceedings.mlr.press/v162/choromanski22a.html", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable feedback. Below we group related points in Weaknesses (W) and Questions (Q). \n\n> **Q1 & W2: Optimal baseline results**\n\nWe have to respectfully point out the factual errors from the reviews. **The suggested work [1] does not experiment on the largest graph ogbn-papers100M**, and for ogbn-proteins, [1] uses their own splits (by subgraph partition) instead of standard OGB splits, so **not directly comparable to us**. Besides, **SIGN [2] reports the optimal test acc 65.11±0.14 on ogbn-papers100M (see Table 8 of [2]), rather than 69.84 as suggested by the reviewer (which should be SIGN's validation acc)**. In Table 3, our test score 66.01 ± 0.37 is significantly higher than their optimal test acc. Given the benchmark setting we used and fair comparison with strong competitors (including two recent efficient graph Transformers NodeFormer/ANS-GT), our achieved gains are non-trivial, as resonated by other reviewers.\n\n[1] Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification\n\n[2] SIGN: Scalable Inception Graph Neural Networks\n\n> **Q1 & W2: Compare with GraphGPS and other attentions**\n\nWe tried replacing our attention with GraphGPS's on large graphs in Table 3, and unfortunately, the model suffers OOM with a 24GB GPU. The scalability issue of GraphGPS on these large-sized graphs is also encountered by [3] (see their Table 2). Nevertheless, we add comparison with GraphGPS on medium-sized graphs, and found our model achieves significantly higher scores (see results in Table 1 of the uploaded PDF).\n\nFor other attentions (NodeFormer and GAT), we have compared with them in Table 6 which again shows the superiority of our attention.\n\n[3] GOAT: A Global Transformer on Large-scale Graphs\n\n> **Q2 & W3: Positional embeddings (PE) and role of GNNs**\n\nOur claim \"the model does not require PE\" is not violated by the used GNNs, since **GNNs are commonly not recognized as PE in existing literature**. E.g. GraphTrans [4] uses GNNs as a module and claims their model does not require PE. In common sense, PE often refers to the Laplacian features for each node (absolute PE [5]) or distance encodings for node pairs (relative PE [6]), different from GNNs. The PE and GNNs are also distinguished by [7].\n\n[4] Representing long-range context for graph neural networks with global attention\n\n[5] A generalization of transformer networks to graphs\n\n[6] Do transformers really perform bad for graph representation?\n\n[7] Transformer for graphs: An overview from architecture perspective\n\n> **Q2 & W4: Performance degrades without GNNs**\n\nIt is natural to see performance drop w/o GNN, since in our model GNN can additionally use input graphs complementary to global attention. Having said that **the one-layer global attention plays a crucial role in our model** for achieving its first-rank results in Table 2 and 3 over pure GNNs and powerful Transformers (including GraphTrans that also uses GNN). This suggests our proposed attention contributes to the gains that are much more difficult to achieve over the GNN baseline.\n\nFurthermore, **our claim \"a one-layer attention can bring up competitive performance\" is originally stated within the context of graph Transformers, wherein peer models use deep attentions and PE (or GNN as an alternative). Our viewpoint lies in the advances over existing models, and our simple attention can significantly enhance the scalability on large graphs**. Based on our empirical evidence and acknowledgement by other reviewers, we believe this claim is properly justified.\n\n> **Q3 & W1: Compare with softmax attention**\n\nThe softmax attention that requires $O(N^2)$ cannot scale to large graphs, so we add some comparison on small graphs in Table 2 of the uploaded PDF. It shows softmax attention yields undesired results, possibly because the softmax would lead to gradient vanishing when N is large, as observed by NodeFormer. In terms of our attention, we do not observe any obvious inability (see some visualization results in Fig. 1 of the uploaded PDF).\n\n> **Q4: Expressiveness of one-layer attention**\n\nThe one-layer attention is expressive enough for learning arbitrary all-pair interactions as done by the multi-layer model, as discussed in Sec 6 from signal denoisng perspective. Also notice that in our model, the one-layer attention does not mean using one-layer neural network, and one can stack multiple feedforward NN layers on top of the attention if needed. In this way, **the model can still have enough capacity for learning complex functions**. \n\nFor pretraining tasks, which is orthogonal to our current focus as well as the peer models we compare in this area, we leave this extension as future works.\n \n> **Q5: Low-pass filter for Eqn. 5**\n\nThank you for bringing up this inquiry. However, we humbly point out that **Eqn. 5 is not a low-pass smoothing objective, nor was it referenced as that within our paper**. Actually, as illustrated in Sec 5, Eqn. 6 aims to adaptively smooth node features for different pairs and it enforces smoothing effect on arbitrary node pairs (instead of neighboring nodes). In this sense, the model is not a traditional low-pass filter (as GCN), and can adaptively leverage high-order information. \n\n> **W5: Mini-batch training for large graphs**\n\nThe sampling technique is a common practice for training on large graphs, and adopted by peer models as it is prohibitive to fit a large graph into a GPU at the first place. While other models require sophisticated sampling, our used random mini-batch is much simpler and requires almost no extra time. Compared to NodeFormer that also uses mini-batch training on large graphs, SGFormer costs 3x fewer training time on ogbn-products, which suggests **our efficiency improvement purely stems from the simplified architecture with one-layer attention**. The latter are indeed our contributions.\n\nWe will add the suggested reference in revision. Please let us know if you had further questions."}]

Author rebuttal:
Dear Area Chairs and Reviewers,

We thank the reviewers for their time, thorough reviews and constructive suggestions. Overall, the reviewers deemed our work well written, the method novel and the results solid. Below we first restate our main contributions and distill the reviewers' comments to facilitate the discussions. 

**1. We reassess the need for deep attention layers when learning representations on large graphs, and propose Simplified Graph Transformers that unlock the potential of one-layer global attention for large graphs where the scalability matters.**

>Most of the reviewers appreciated our motivation/methodology with the comments (R**J3Wh**:"the simplicity of the method is appreciated", R**9PQr**:"the idea and the design of the simple global attention is novel", R**moxf**:"SGFormer simplifies the design philosophy for Transformers on large graphs").

**2. Despite the simplicity, our model shows highly competitive results across diverse node property prediction benchmarks and its superior scalability to graph sizes ranging from 2K to 0.1B, and yields up to 37x/141x speedup for training/inference over efficient graph Transformers.**

> Most of the reviewers recognized our results significant with the comments (R**J3Wh**:"Results are very strong in terms of model quality and performance", R**9PQr**:"The proposed SGFormer is efficient and scalable", R**moxf**:"The empirical results look promising")

**3. As a justification, we provide theoretical insights into why the one-layer attention model can be a powerful graph learner through the lens of signal denoising perspectives.** 

> R**moxf** acknowledged that our analysis "can help in understanding and improving the approach". R**9PQr** inquires the potential extension of our results and we show how to generalize the analysis in the individual response.

While R**bWXq** raised questions on our comparison results and asked for more empirical justifications, we identify some factual errors in the quoted scores and concept descriptions which may have led to the reviewer's misinterpretations regarding our claims and results. We clarify and provide detailed elaboration in the separate rebuttal.

We upload a one-page PDF that contains new experimental results as suggested by the reviewers. In the following individual response, we provide answers to each raised weakness/question points and will incorporate the suggestions and new results in our revised paper.

Best regards,

Authors of Submission 11333

Meta-review: This paper presents the Simplified Graph Transformers (SGFormer) for graph representations learning. The method greatly simplifies the training process in prior work and achieves good performance on several tasks. Since all reviewers are positive, I am happy to accept the paper.
Decision: Accept (poster)