Do Transformers Really Perform Badly for Graph Representation?
Authors: Chengxuan Ying
Tianle Cai
Shengjie Luo
Shuxin Zheng
Guolin Ke
Di He
Yanming Shen
Tie-Yan Liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Transformer
Graph Representation
OGB-LSC

Abstract: The Transformer architecture has become a dominant choice in many domains, such as natural language processing and computer vision. Yet, it has not achieved competitive performance on popular leaderboards of graph-level prediction compared to mainstream GNN variants. Therefore, it remains a mystery how Transformers could perform well for graph representation learning. In this paper, we solve this mystery by presenting Graphormer, which is built upon the standard Transformer architecture, and could attain excellent results on a broad range of graph representation learning tasks, especially on the recent OGB Large-Scale Challenge. Our key insight to utilizing Transformer in the graph is the necessity of effectively encoding the structural information of a graph into the model. To this end, we propose several simple yet effective structural encoding methods to help Graphormer better model graph-structured data. Besides, we mathematically characterize the expressive power of Graphormer and exhibit that with our ways of encoding the structural information of graphs, many popular GNN variants could be covered as the special cases of Graphormer. The code and models of Graphormer will be made publicly available at \url{https://github.com/Microsoft/Graphormer}.

Do Transformers Really Perform Bad for Graph Representation?
Chengxuan Ying', Tianle Cai², Shengjie Luo Shuxin Zheng" ! Guolin Ke* Di He Yanming Shen', Tie-Yan Yan Liu"
Dalian University of Technology "Princeton University
Peking University *Microsoft Research Asia
yingchengssnuanggaall com, tianle. caiéprinceton edu, luosj@stu pku. eau.edu.com {shuz) guoke, dihe,, (yliu)@microoose com, shen@dlut. .du.te.dd.cccm
Abstract
The Transformer architecture has become dominant choice in many domains, such natural language processing and computer vision. Yet, it has not achieved com- petitive performance on popular leaderboards of graph-level prediction compared mainstream GNN variants. Therefore, remains mystery how Transformers could perform well for graph representation learning. In this paper, we solve this mystery by presenting Graphormer, which built upon the standard Transformer architecture, and could attain excellent results on a broad range of graph representa- tion learning tasks, especially on the recent OGB Large-Scale Scale Challenge. Our key insight to utilizing Transformer in the graph is the necessity of effectively encoding the structural information of graph into the model. To this end, we propose several simple yet effective structural encoding methods to help Graphormer better model graph-structure data. Besides, we mathematically characterize the expressive power of Graphormer and exhibit that with our ways of encoding the structural information of graphs, many popular GNN variants could be covered as the special cases of Graphormer. The code and models of Graphormer will be made publicly available at lhtps:: :/gs //gi ///gtttt...../// com/Mi htt.///rrooooftraaprooooooa
Introduction
The Transformer 446 well acknowledged as the most powerful neural network in modelling sequential data, such natural language [ 35| 6 and speech [17]. Model variants built upon
Transformer have also been shown great performance in computer vision [12, 36 and programming
language 119 57 41). However, the best of our knowledge, Transformer has still not been the de-facto standard on public graph representation leaderboards [22] 14 2II. There are many attempts of leveraging Transformer into the graph domain, but the only effective way is replacing some key modules (e.g., feature aggregation) in classic GNN variants by the softmax attention 77 23
56 43 13). Therefore, it is still open question whether Transformer architecture is suitable to model graphs and how to make work in graph representation learning.
48
In this paper, we give affirmative answer by developing Graphormer, which is directly built upon the standard Transformer, and achieves state-of-the-art performance on wide range of graph- level prediction tasks, including the very recent Open Graph Benchmark Large-Scale Challenge (OGB-LSC) [21], and several popular leaderboards (e.g., OGB [22). Benchmarking-Gii (14). The Transformer is originally designed for sequence modeling. To utilize its power in graphs, we believe
IIttrns MSRA.
Coorrespondigg authors.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the key is to properly incorporate structural information of graphs into the model. Note that for each node i, the self- only calculates the semantic similarity between and other nodes, without considering the structural information of a graph reflected on the nodes and the relation between node pairs. Graphormer incorporates several effective structural encoding methods to leverage such information, which are described below.
First, we propose a Centrality Encoding in Graphormer to capture the node importance in the graph. In a graph, different nodes may have different importance, e.g. celebrities are considered to be more influential than the majority of web users in a social network. However, such information isn't 't reflected in the self-attention module as it calculates the similarities mainly using the node semantic features. To address the problem, we propose to encode the node centrality in Graphormer. In particular, we leverage the degree centrality for the centrality encoding, where learnable vector assigned to each node according to its degree and added to the node features in the input layer. Empirical studies show that simple centrality encoding is effective for Transformer in modeling the graph data.
Second, we propose a novel Spatial Encoding in Graphormer to capture the structural relation between nodes. One notable geometrical property that distinguishes graph-structured data from other structured data, e.g., language. images, is that there does not exist a canonical grid to embed the graph. In fact, nodes can only lie in non-Euclidean space and are linked by edges. To model such structural information, for each node pair. we assign learnable embedding based on their spatial relation. Multiple measurements in the literature could be leveraged for modeling spatial relations. For a general purpose, we use the distance of the shortest path between any two nodes as a demonstration, which will be encoded as bias term in the softmax attention and help the model accurately capture the spatial dependency in a graph. In addition, sometimes there is additional spatial information contained in edge features, such as the type of bond between two atoms in a molecular graph. We design a new edge encoding method to further take such signal into the Transformer layers. To be concrete, for each node pair, we compute an average of dot-products of the edge features and learnable embeddings along the shortest path, then use it in the attention module. Equipped with these encodings, Graphormer could better model the relationship for node pairs and represent the graph.
By using the proposed encodings above, we further mathematically show that Graphormer has strong expressiveness as many popular GNN variants are just its special cases. The great capacity of the model leads to state-of-the -art performance on a wide range of tasks in practice. On the large-scale quantum chemistry regression datase[] in the very recent Open Graph Benchmark Large-Scale Challenge (OGB-LSC) 121], Graphormer outperforms most mainstream GNN variants by more than 10% points in terms of the relative error. On other popular leaderboards of graph representation learning (e.g.. MolHIV, MolPCBA, ZINC) 22 14, Graphormer also surpasses the previous best results, demonstrating the potential and adaptability of the Transformer architecture.
2 Preliminary
In this section, we recap the preliminaries in Graph Neural Networks and Transformer.
Graph Neural Network (GNN). Let =
= (V, E) denote a graph where V = {or, U2,... un [V] is the number of nodes. Let the feature vector of node e; be 2;. GNNs aim to learn representation of nodes and graphs. Typically, modern GNNs follow a learning schema that iteratively updates the representation of node by aggregating representations of its first or higher-order neighbors. We denote 1,,") as the representation of v; at the 1-th layer and define n:
xyz The I-th
iteration of aggregation could be characterized by AGGREGATE-
step
01
AGGREGATE (1) (EE-))))(())))
1 (1) COMBINE (1)
(1) (M aa
(1)
where (e;)) is the set of first higher-order neighbors of 02. The AGGREGATE function is used to gather the information from neighbors. Common aggregation functions include MEAN MAX, SUM, which are used in different architectures of GNNs [26 18, 47 50) The goal of COMBINE function
is to fuse the information from neighbors into the node representation.
https::/ogb.... htttps://ogb.stanford.oo stw.sordddddooooo http////r..///////d/////////gog.

---

04 Us
0/1
MatMul
4/2
413
SoftMax
1/4
06
Scale
Spatial Encoding
2/1
2/2
vy V4 V/
MatMul
0/2
Linear
Linear
Linear
973
K
Edge Encoding
Node Feature
Centrality Encoding
Figure 1: An illustration our proposed centrality encoding. spatial encoding, and edge encoding in Graphormer.
In addition, for graph representation tasks, a READOUT function is designed to aggregate node features h (L) of the final iteration into the representation hGg of the entire graph G:
hg READOUT 1 mm)))
|
(2)
READOUT can be implemented by a simple permutation invariant function such as summation [50] sophisticated graph-level pooling function (1]
Transformer. The Transformer architecture consists of composition of Transformer layers [46] Each Transformer layer has two parts: self-attention module and a position-wise feed-forward network (FFN). Let H [h] ... A the hidden dimension and h; R 1xd d is the hidden representation at position The input H is projected by three matrices WQ E Rdxdx WK E Idxxx and Wy E pdxdy to the corresponding representations K, V. The self-attention is then calculated as:
R denote the input of self-attention module where d
Q HWQ,
K HWW: V HWV.
(3)
QK
A = Vdk
Attn (H) softmax (A) V,
(4)
where A is a matrix capturing the similarity between queries and keys. For simplicity of illustration, consider the single-head self-attention and assume dx dy d. The extension the multi-head attention is standard and straightforward, and we omit bias terms for simplicity.
Graphormer
In this section, we present our Graphormer for graph tasks. First, we elaborate on several key designs in the Graphormer, which serve as an inductive bias in the neural network to learn graph representation. We further provide the detailed implementations of Graphormer. Finally, we show that our proposed Graphormer is more powerful since popular GNN models 26 are its special cases.

---

3.1 Structural Encodings in Graphormer
As discussed in the introduction, it is important to develop ways to leverage the structural information of graphs into the Transformer model. To this end, we present three simple but effective designs of encoding in Graphormer. See Figure for an illustration.
3.1.1 Centrality Encoding
In 4 the attention distribution calculated based on the semantic correlation between nodes. However, node centrality, which measures how important node is in the graph, is usually strong signal for graph understanding, For example, celebrities who have a huge number of followers are important factors in predicting the trend of a social network [38] 37]. Such information is neglected in the current attention calculation, and we believe it should be a valuable signal for Transformer models.
In Graphormer, we use the degree centrality, which is one of the standard centrality measures in literature, as an additional signal to the neural network. To be specific, we develop Centrality Encoding which assigns each node two real-valued embedding vectors according to indegree and outdegree. As the centrality encoding is applied to each node, we simply add it to the node features as the input.
h (0) = + "dgg (ps) + 2+ "deg" (wx)
(5)
where 2 E Rd are learnable embedding vectors specified by the indegree deg (v;) and out- degree deg (vz) respectively. For undirected graphs, deg (t;) and deg (ux) could be unified to deg(v:). By using the centrality encoding in the input, the softmax attention can catch the node importance signal in the queries and the keys. Therefore the model can capture both the semantic correlation and the node importance in the attention mechanism.
3.1.2 Spatial Encoding
An advantage of Transformer is its global receptive field. In each Transformer layer, each token can attend to the information at any position and then process its representation. But this operation has a byproduct problem that the model has to explicitly specify different positions encode the positional dependency (such as locality) in the layers. For sequential data, one can either give each position an embedding (i.e., absolute positional encoding [46) the input encode the relative distance of any two positions (i.e., relative positional encoding 42 in the Transformer layer.
However, for graphs, nodes are not arranged as a sequence. They can lie in multi-dimensional spatial space and are linked by edges. To encode the structural information of a graph in the model, we propose novel Spatial Encoding. Concretely, for any graph G, we consider a function (1,, Uy)) : V x V + IR which measures the spatial relation between 0; and vy in graph G. The function can be defined by the connectivity between the nodes in the graph. In this paper, choose o(0, 27) to be the distance of the shortest path (SPD) between U, and vy if the two nodes connected. If not, set the output of & to be special value, i.e., -1. We assign each (fcasible) output value a learnable scalar which will serve as a bias term in the self-attention module. Denote Ai as the (i, feeeemet of the Query-Key product matrix A, we have:
A., (hy Vd
bo(r).))))
(6)
where by(e),y)) is a learnable scalar indexed by o(v, U;), and shared across all layers.
Here we diseuss several benefits of our proposed method. First, compared to conventional GNNs described in Section 2, where the receptive field is restricted to the neighbors, we can see that in Eq. (6), the Transformer layer provides a global information that each node can attend to all other nodes in the graph. Second, by using be(e..ry). each node in single Transformer layer can adaptively attend to all other nodes according to the graph structural information. For example, if bo(e.re) is learned to be a decreasing function with respect to Φfv,, wy), for each node, the model will likely pay more attention to the nodes near it and pay less attention to the nodes far away from it.

---

3.1.3 Edge Encoding in the Attention
In many graph tasks, edges also have structural features, e.g., in molecular graph, atom pairs may have features describing the type of bond between them. Such features are important to the graph representation, and encoding them together with node features into the network is essential. There are mainly two edge encoding methods used in previous works. the first method, the edge features are added to the associated nodes' features [22 30]. In the second method, for each node, its associated edges' features will be used together with the node features in the aggregation [15] 50, 26). However, such ways of using edge feature only propagate the edge information to its associated nodes, which may not be an effective way to leverage edge information in representation of the whole graph.
To better encode edge features into attention layers, we propose a new edge encoding method in Graphormer. The attention mechanism needs to estimate correlations for each node pair (1), 11)), and we believe the edges connecting them should be considered in the correlation as in [34 48] For each ordered node pair (Vi, Uj), we find (one of) the shortest path SP,j = (+1, E2, eN) from & to Vij, and compute an average of the dot-products of the edge feature and a learnable embedding along the path. The proposed edge encoding incorporates edge features via a bias term to the attention module. Concretely, we modify the (elemett of A in Eq. (3) further with the edge encoding Cij as:
A, = (h; (Wx Vd
N Σ Fe,
bocon)s) + Cij. where Cij
N
where Fe., is the feature of the n-th edge en in SP Spyj wh RRdg is the n-th weight embedding, and dg is the dimensionality of edge feature.
3.2 Implementation Details of Graphormer
Graphormer Layer. Graphormer is built upon the original implementation of classic Transformer encoder described [46]. In addition, we apply the layer normalization (LN) before the multi-head self-attention (MHA) and the feed-forward blocks (FFN) instead of after 49 This modification
has been unanimously adopted by all current Transformer implementations because it leads to more effective optimization [40]. Especially, for FFN sub-layer, we set the dimensionality of input, output, and the inner-layer to the same dimension with d. We formally characterize the Graphormer layer as below:
(0 (HA(LN(((-D)) + (1-1) 0 (FN (()) + +h'0)
(8)
(9)
Special Node. As stated in the previous section, various graph pooling functions are proposed to represent the graph embedding. Inspired by (15. in Graphormer, we add special node called [VNode] to the graph, and make connection between [VNode] and each node individually. In the AGGREGATE-COMBING
step, the representation of [VNode] has been updated as normal nodes in graph, and the representation of the entire graph lGg would be the node feature of [VNode] in the final layer. In the BERT model 35), there is a similar token, i.e., [CLS], which is special token attached at the beginning of each sequence, to represent the sequence-level feature on downstream tasks. While the [VNode] is connected to all other nodes in graph, which means the distance of the shortest path is for any @[VNode), uz) and o(v, [VNode]] ). the connection is not physical. To distinguish the connection of physical and virtual, inspired by 225, we reset all spatial encodings for b, and [VMode)) to a distinct learnable scalar.
3.3 How Powerful is Graphormer?
In the previous subsections, we introduce three structural encodings and the architecture of Graphormer. Then a natural question is: Do these modifications make Graphormer more pow- erful than other GNN variants? In this subsection, we first give an affirmative answer by showing that Graphormer can represent the AGGREGATE and COMBINE steps in popular GNN models:
5

---

Fact 1. By choosing proper weights and distance function é. the Graphormer layer can represent AGGREGATE and COMBINE steps of popular GNN models such as GIN, GCN, GraphSAGE.
The proof sketch to derive this result is: 1) Spatial encoding enables self-attention module to distinguish neighbor N (v;) of node U; so that the softmax function can calculate mean statistics over N (v;); 2) Knowing the degree of node, mean over neighbors can be translated to sum over neighbors: 3) With multiple heads and FFN, representations of 8 and N (14) can be processed separately and combined together later. We defer the proof of this fact to Appendix A.
Moreover, we show further that by using our spatial encoding, Graphormer can go beyond classic message passing GNNs whose expressive power is no more than the Wreisfeiler-eehmee (WL) test. We give concrete example in Appendix A to show how Graphormer helps distinguish graphs that the W- test fails to.
Connection between Self-attention and Virtual Node. Besides the superior expressiveness than popular GNNs, also find interesting connection between using self-attention and the virtual node heuristic 15 31 24 22] As shown in the leaderboard of OGB [22], the virtual node trick, which augments graphs with additional supernodes that are connected to all nodes in the original graphs, can significantly improve the performance of existing GNNs. Conceptually, the benefit of the virtual node is that it can aggregate the information of the whole graph (like the READOUT function) and then propagate it to each node. However, a naive addition of supernode to a graph can potentially lead inadvertent over-smoothing of information propagation (24). We instead find that such a graph-level aggregation and propagation operation can be naturally fulfilled by vanilla self self-attention without additional encodings. Concretely, we can prove the following fact:
Fact 2. By choosing proper weights, every node representation of the output of a Graphormer layer without additional encodings can represent MEAN READOUT functions.
This fact takes the advantage of self-attention that each node can attend to all other nodes. Thus can simulate graph-level READOUT operation to aggregate information from the whole graph. Besides the theoretical justification, we empirically find that Graphormer does not encounter the problem of over-smoothing, which makes the improvement scalable. The fact also inspires us to introduce a special node for graph readout (see the previous subsection).
4 Experiments
We first conduct experiments on the recent OGB-LSC 21 quantum chemistry regression (i.c.,
PCQM4M-LSC) challenge, which is currently the biggest graph-level prediction dataset and contains more than 3.8M graphs in total. Then, we report the results on the other three popular tasks: ogbg- molhiv, gebg-molpeba and ZINC, which come from the OGB [22] and benchmarking GNN [14] leaderboards. Finally, we ablate the important design elements of Graphormer. A detailed description of datasets and training strategies could be found in Appendix B.
4.1 OGB Large-Scale Challenge
Baselines. We benchmark the proposed Graphormer with GCN 26 and GIN [50] and their variants with virtual node (-VN) [5] They achieve the tate-offthh--an valid and test mean absolute error (MAE) on the official leaderboard 21.. In addition, we compare to GIN's multi-hop variant (5), and 12-layer deep graph network DeeperGCN (30), which also show promising performance on other leaderboards. We further compare our Graphormer with the recent Transformer-based graph model
GT 13
Settings. We primarily report results two model sizes: Graphormer (I. 12, d = 768), and a smaller one GraphormerSMAu (L = 6, d = 512). Both the number of attention heads in the attention module and the dimensionality of edge features dE are set to 32. We use AdamW as the optimizer, and set the hyper-parameter e to 1e-8 and (31, to (0.99,0.999) The peak learning rate set to 2c-4 (3e-4 for GraphormersMALl) with a 60k-step warm-up stage followed by linear decay learning rate scheduler. The total training steps are 1M. The batch size is set to 1024. All models are trained on 8 NVIDIA V100 GPUS for about 2 days.

---

Table 1: Results on PCQM4M-LSC. indicates the results are cited from the official leaderboard 21
method
#param.
train MAF
validate MAF
GCN
26
2.0M
0.1318
0.1691 (0.1684*)
GIN
50
3.8M
0.1203
0.1537 (0.1536*)
GCN-VN
26
15
4.9M
0.1225
0.1485 (0.1510*)
GIN-VN
50
15
6.7M
0.1150
0.1395 (0.1390) )
GINE-vN
5
15
13.2M
0.1248
0.1430
DeeperGCN-vy
30
15
25.5M
0.1059
0.1398
GT LB
0.6M
0.0944
0.1400
GT--ide
I3
83.2M
0.0955
0.1408
GraphormeTssauu
12.5M
0.0778
0.1264
Graphormer
47.1M
0.0582
0.1234
Results. Table summarizes performance comparisons on PCQM4M-LSC dataset. From the table, GIN-vN achieves the previous ttate-of-the-ar validate MAE of 0315 The original implementation of GT [3] employs a hidden dimension of 64 reduce the total number of parameters. For fair comparison, we also report the result by enlarging the hidden dimension to 768, denoted by -ide which leads to a total number parameters of 83.2M. While, both GT and GT-wide do not outperform GIN-vN and DeeperGGN-vv. Especially, we do not observe performance gain along with the growth of parameters of GT.
Compared to the previous state-of-the-ar GNN architecture, Graphormer noticeably surpasses GIN- VN by a large margin, e.g., 11.5% relative validate MAE decline. By using the ensemble with ExpC [5]]. we got 0.1200 MAE on complete test set and won the first place of the graph-level track in OGB Large-Scale Challenge 21 53) As stated Section 3.3 we further find that the proposed Graphormer does not encounter the problem of over- wer-smoothingg i.e., the train and validate error keep going down along with the growth of depth and width of models.
4.2 Graph Representation
In this section, we further investigate the performance of Graphormer on commonly used graph-level prediction tasks of popular leaderboards, i.e., OGB [22] (OGBG-MoIPCBA, OGBG-MolHIV), and benchmarking-GGN
14 (ZINC). Since pre-training is encouraged by OGB, we mainly explore the transferable capability of a Graphormer model pre-trained on OGB-LSC (i.e., PCQM4M-LSC). Please note that the model configurations, hyper-parameter pre- pre-trained Graphormers used for MolPCBA and MolHIV are different from the models used in the previous subsection. Please refer to Appendix B for detailed descriptions. For benchmarking. GNN, which does not encourage large pre-trained model, we train an additional Graphormers (I = 12, d = 80, total param.= 489K)) K from scratch on ZINC.
and the pre-training performance of
Baselines. We report performance of GNNs which achieve top- peppeorormance on the official leader- board without additional Comain-specipy features. Considering that the pre-trained Graphormer leverages external data, for a fair comparison on OGB datasets, we additionally report performance for fine-tuning GIN-vN pre-trained on PCQM4M-ISSC dataset, which achieves the previous state-of- the-art valid and test MAE on that dataset.
Settings. We report detailed training strategies in Appendix B. In addition, Graphormer is more easily trapped in the over- fitting problem due the large size of the model and the small size of the dataset. Therefore, we employ widely used data augmentation for graph FLAG [27], to mitigate over-fitting problem on OGB datasets.
Results. Table 2 3 and summarize performance of Graphormer comparing with other GNNs on MolHIV, MolPCBA and ZINC datasets. Especially, GT [33 and SAN (2 Table recently proposed Transformer-based GNN models. Graphormer consistently and significantly outperforms previous state-of-the-art GNNs on all three datasets by a large margin. Specially, except Graphormer,
edu/ http:////.aaaaooooooo//////////p
http://hhhh.ccmgrgagaeggggggeeee httpa//wwwoooooo/oooooo//oo/aaea http://wwww.aaaa////////attttttr Leaderboards.ng md

---

Table 2: Results on MolPCBA.
Table 3; Results on MolHIV.
method
#param.
(P
method
#param.
AUC (%)
DeeperGCNN-ye -VVN-FFAG FLAG
5.6M
28.42++0.43
X
526K
78.83+1.00
DGN
6.7M
28.85-+0.30
PNA 10
326K
79.05=+1.32
GINE-VN
S
6.1M
29.17:10.15
PHC-GNN 29
111K
79.34:11.16
PHIC-GNN 29
1.7M
29.47110.26
DeeP 30
532K
79.42.11.20
GINE-APPNP
S
6.1M
29.79-10.30
DGN
2
114K
79.70.10.97
GIN-VN 50 (fine-tune)
3.4M
29.02=+0.17
GIN-VN 50) (fine-tune)
3.3M
77.80=1182
Graphormer FLAG
119.5M
01.39=0..2
Graphormer-Fue
47.0M
80.51=0..3
Table 4: Results on ZINC.
method
#param.
lest MAE
GIN [50]
509,549
0.526=0.051
GraphSage [8
505,341
0.398
GAT
531,345
0.084
GCN 26
505,079
0.007110001
GatedGCN PE
4
505,011
0.214#0.006
MPNN (sum)
15
480,805
0.145
PNA [0]
387.155
0.142
GT [33
588,929
0.2261000014
SAN (28
508, 577
0.009
GraphormersLLI
489,321
0.122
the other pre-trained GNNs not achieve competitive performance, which is in line with previous literature [20]. In addition, we conduct more comparisons to fine-tuning the pre-trained GNNs, please refer to Appendix
4.3 Ablation Studies
We perform series of ablation studies on the importance of designs in our proposed Graphormer, on PCQM4M-LSC dataset. The ablation results are included in Table To save the computation resources, the Transformer models in table have 12 layers, and are trained for 100K iterations.
Node Relation Encoding. We compare previously used positional encoding (PE) our proposed spatial encoding, which both aim to encode the information of distinct node relation to Transformers. There are various PEs employed by previous Transformer-baser GNNs, e.g., Weisfeiler-Lehmnn PE (WL-PE) [56] and Laplacian PE [3] 14]. We report the performance for Laplacian PE since performs well comparing
series of PEs for Graph Transformer in previous literature (I3] Transformer architecture with the spatial encoding outperforms the counterpart built on the positional encoding, which demonstrates the effectiveness of using spatial encoding to capture the node spatial information.
Centrality Encoding. Transformer architecture with degree-base centrality encoding yields a large margin performance boost in comparison those without centrality information. This indicates that the centrality encoding is indispensable to Transformer architecture for modeling graph data.
Edge Encoding. We compare our proposed edge encoding (denoted as via attn bias) to two commonly used edge encodings described in Section 3.1.3 incorporate edge features into GNN, denoted as node and via Aggr in Table From the table, the gap of performance is minor between the two conventional methods, but proposed edge encoding performs significantly better, which indicates that edge encoding as attention bias is more effective for Transformer to capture spatial information on edges.

---

Table 5:
Ablation study results on PCQM4M-LSC dataset with different designs.
Node Relation Encoding
Edge Encoding
Centrality
valid MAE
Laplacian PE
Spatial
via node
via Aggr
via atin bias(Eq 7
0.2276
0.1483
/
0.1427
/
0.1396
0.1328
/
0.1327
0.1304
5
Related Work
In this section, we highlight the most recent works which attempt to develop standard Transformer architecture- based GNN or graph structural encoding, but spend less effort on elaborating the works by adapting attention mechanism to GNNs 33 55
56 45
5.1 Graph Transformer
There are several works that study the performance of pure Transformer architectures (stacked by transformer layers) with modifications on graph representation tasks, which are more related to our Graphormer. For example, several parts of the transformer layer are modified in [43], including an additional GNN employed in attention sub-layer to produce vectors of Q, K, and V, long-range residual connection, and two branches of FFN to produce node and edge representations separately, They pre-train their model on 10 million unlabelled molecules and achieve excellent results by fine-tuning on downstream tasks. Attention module is modified
soft adjacency matrix in [39 computed inter-atomic distance matrix to the
by directly adding the udjacency matrix and RDKi
attention probabilites. Very recently, Dwivedi al. 13 revisit series of works for Transformer- based GNNs, and suggest that the attention mechanism in Transformers on graph data should only aggregate the information from neighborhood (i.e., using adjacent matrix as attention mask) to ensure graph sparsity, and propose to use Laplacian eigenvector as positional encoding. Their model GT surpasses baseline GNNs on graph representation task. A concurrent work (28) propose novel full Laplacian spectrum to learn the position of each node in graph, and empirically shows better results than GT.
5.2 Structural Encodings in GNNs
Path and Distance in GNNs. Information of path and distance is commonly used in GNNs. For example, an attention-based aggregation is proposed in [ where the node features, edge features, one-hot feature of the distance and ring flag feature are concatenated to calculate the attention probabilites; similar to [9. path- path-based attention leveraged in [52] model the influence between the center node and its higher-order neighbors; a distance-weighte
aggregation scheme on graph is proposed in (54); it has been proved in 332 that adopting distance encoding (i.e., one-hot feature of the distance extra node attribute) could lead to strictly more expressive power than the 1-WL test.
Positional Encoding in Transformer on Graph. Several works introduce positional encoding (PE) to Transformer-basee GNNs to help the model capture the node position information. For example, Graph-BERT (56) introduces three types of PE to embed the node position information to model, i.e. an absolute WL-PE which represents different nodes labeled by Weisfeiler- algorithm, an intimacy based PE and a hop based PE which are both variant to the sampled subgraphs. Absolute Laplacian PE is employed in 13 and empircal study shows that its performance surpasses the absolute WL-PE used [56]
Except the conventionally used methods to encode edge feature, which are described in previous section, there are several attempts that exploit how to better encode edge features: an attention-based GNN layer is developed in [16] to encode edge features, where the edge feature
Edge Feature.
hhttps:// tettps::/www.... rrkit. org/

---

is weighted by the similarity of the features of its two nodes; edge feature has been encoded into the popular GIN [50] in [3]; in [3]. the authors propose to project edge features to an embedding
vector, then multiply it by attention coefficients, and send the result to an additional FFN sub-layer to produce edge representations;
6 Conclusion
We have explored the direct application of Transformers to graph representation. With three novel graph structural encodings, the proposed Graphormer works surprisingly well on wide range of popular benchmark datasets. While these initial results are encouraging, many challenges remain. For example, the quadratic complexity of the self-attention module restricts Graphormer's application on large graphs. Therefore, future development of efficient Graphormer is necessary. Performance improvement could be expected by leveraging domain knowledge- graph datasets. Finally, an applicable graph sampling strategy is desired for node representation extraction with Graphormer. We leave them for future works.
encodings particular
References
[1] Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. ICLR, 2021.
[2] Dominique Beaini, Saro Passaro, Vincent Létourncau, William L Hamilton, Gabricle Corso, and Pietro
Liö. Directional graph networks. In International Conference on Machine Learning, 2021.
[3] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representa- tion. Neural computation, 13(6):1373-1366 2003.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint 17X
2017.
[5] Rémy Brossard, Oriel Frigo, and David Dehaene. Graph convolutions that can finally model local structure. arXiv preprint arXiv:2011. 2020.
[6] Tom Brown, Benjamin Mann. Nick Ryder. Melanie Subbiah, Jared D 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 Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Syxtems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[7] Deng Cai and Wai Lam. Graph transformer for graph-to- sequueec learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7464-7477 7471, 2020.
[8] Tianle Cai,, Shengjie Luo, Keyulu Xu, Di He, Tic-yan Liu, and Liwei Wang. Graphnorm: principled approach to accelerating graph neural network training. In International Conference on Machine Learning, 2021.
[9] Benson Chen, Regina Barzilay, and Tommi Jaakkola. Path-augmented graph transformer network. arXiv preprint arXiv: 1905. 12712, 2019.
[10] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbour- hood aggregation for graph nets. Advances in Neural Information Processing Systems, 33, 2020.
[11] Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidi- rectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pages 4171-4186, 2019.
[12] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words:
Transformers for image recognition scale. arXiv preprint arXiv:2010.1 109.,999.,, 2020.
[13] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
[14] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Bench- marking graph neural networks. arXiv preprint arXiv:2003.009%. 2020.
10

---

[15] Justin Gilmer, Samuel S Schoenholz. Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, pages 1263-1272. PMLR, 2017.
[16] Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pages 9211-9219, 2019.
[17] Anmol Gulati, James Qin. Chung- -heng Chiu, Niki Parmar, Yu Zhang. Jiahui Yu, Wei Han, Shibo Wang. Zhengdong Zhang. Yonghui Wu, et al. Conformer: Convolation-augmeente transformer for speech recognition. arXiv preprint arXiv:2005.88/
2020.
[18] William L Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
[19] Vincent Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global relational models of source code. In International conference learning representations, 2019.
[20] W Hu, Liu. Gomes, M Zitaik, P Liang. V Pande, and J Leskovec. Strategies for pre- pre-training graph neural networks. In International Conference on Learning Representations (ICI.R), 2020.
[21] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: large-scale challenge for machine learning on graphs. arXiv preprint (xXXx:2103.09433 2021.
[22] 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. arXiv preprint arXiv:200500068/ 2020.
[23] Ziniu Hu. Yuxiao Dong, Kuansan Wang. and Yizhou Sun. Heterogeneous graph transformer. Proceedings of The Web Conference 2020, pages 2704-2710, 2020.
[24] Katsuhiko Ishiguro, Shin-ichi Maeda, and Masanori Koyama. Graph warp module: an auxiliary module for boosting the power of graph neural networks in molecular graph analysis. arXiv preprint arXiv: 2019.
[25] Guolin Ke, Di He, and Yan Liu. Rethinking the positional encoding in language pre-training. ICLR, 2020.
[26] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint /609::6609.000 160966999997 2016.
[27] Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Flag: Adversarial data augmentation for graph neural networks. arXiv preprint arXiv:2010.0989), 2020.
[28] Devin Kreuzer, Dominique Beaini, William Hamilton, Vincent Létoureau, and Prudencio Tossou, Re- thinking graph transformers with spectral attention. arXiv preprint arXiv:2/06.03893, 2021.
[29] Tuan Le. Marco Bertolini, Frank Noé, and Arnrk-Aréé Clevert. Parameterized hypercomplex graph neural networks for graph classification, arXiv preprint arXiv:2 103. 16584, 2021.
[30] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006, 07739, 2020.
[31] Junying Li, Deng Cai, and Xiaofei He. Learning graph-level representation for drug discovery. arXiv preprint arx:: 709.03741,122 2017.
[32] Pan Li. Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33, 2020.
[33] Yuan Li, Xiaodan Liang, Zhiting Hu, Yinbo Chen, and Eric Xing. Graph transformer. 2019.
[34] Xi Victoria Lin, Richard Socher, and Caiming Xiong. Multi-hop knowledge graph reasoning with reward shaping. arXiv preprint 188. 10568, 2018
[35] Yinhan Liu, Myle Ott, Naman Goyal. Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis. Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.1199 2019.
[36] Ze Liu, Yutong Lin, Yue Cao. Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. arXiv preprint 1030:02003.14030. 2021.
[37] P David Marshall. The promotion and presentaiion of the self: celebrity as marker of presentational media. Celebrity studies, 1(1):35-48,, 2010.
[38] Alice Marwick and Danah Boyd. To see and be seen: Celebrity practice on twitter. Convergence, 17(2):139 1180,158822000 2011.
11

---

[39] Lukasz Maziarka, Tomasz Danel. Slawomir Mucha, Krzysztof Rataj. Jacek Tabor, and Stanislaw Jastrzebski. Molecule attention transformer. arXiv preprint arXiv:2002.08264, 2020.
[40] Sharan Narang, Hyung Won Chung. Yi Tay. William Fedus, Thibault Fevry, Michael Matena, Karishma Malkan, Noah Fiedel, Noam Shazeer, Zhenzhong Lan, et al. Do transformer modifications transfer across implementations and applications? arXiv preprint arXiv:2102. 1192,, 2021.
[41] Dinglan Peng. Shuxin Zheng, Yatao Li. Guolin Ke, Di He, and Tie Liu. How could neural networks undorstand programs? In International Conference on Machine Learning. PMLR, 2021.
[42] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified sext-to-text transformer. Journal of Machine Learning Research, 21 (140):1-67, 2020.
[43] Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenhing Huang, and Junzhou Huang. Self- supervised graph transformer on large-scale molecular data, Advances Neural Information Processing Systems, 33, 2020.
[44] Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Pupers), pages 464-668, 2018.
[45] Yunsheng Shi, Zhengjie Huang. Wenjin Wang. Hui Zhong, Shikun Feng, and Yu Sun. Masked label predic- tion: Unified message passing model for semi-supervised classification, arXiv preprint (cXiv2209.03300) 2020.
[46] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NIPS, 2017.
[47] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
[48] Guangtao Wang. Rex Ving, Jing Huang, and Jure Leskovee. Direct multi-hop attention based graph neural network. arXiv preprint arXiv:2009 14332, 2020.
[49] Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the transformer architecture. International Conference on Machine Learning, pages 10524-10533. PMLR, 2020.
[50] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?
In International Conference on Learning Representations. 2019.
[Si] Mingqi Yang. Yanming Shen, Heng Qi, and Baocai Yin. Breaking the expressive bottlenecks of graph neural networks. arXiv preprint arXiv:2012.072.19 2020.
[52] Yiding Yang. Xinchao Wang, Mingli Song. Junsong Yuan, and Dacheng Tao. Spagan: Shortest path graph attention network. Advances in IJCAI, 2019.
[53] Chengxuan Ying. Mingqi Yang. Shuxin Zheng, Guolin Ke, Shengjie Luo, Tianle Cai, Chenglin Wu, Yuxin Wang. Yanming Shen, and Di He. First place solution of kdd cup 2021 & ogb large-scale challenge graph-level track. arXiv preprint wrXiv:2/06.0822 2021.
[54] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International Conference on Machine Learning, pages 7134-7143. PMLR, 2019.
[55] Seongjun Yun. Minbyul Jeong, Rachyun Kim, Jaewoo Kang. and Hyunwoo J Kim. Graph transformer networks. Advances in Neural Information Processing Systems, 32, 2019.
[56] Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.0514 2020.
[S7] Daniel Zügner, Tobias Kirschstein, Michele Catasta, Jure Leskovec, and Stephan Günnemann. Language- agnostic representation learning of source code from structure and context, In International Conference on Learning Representations, 2020.
12


Reviews:
[{"review_id": "Xh1pOl2t8UY", "reviewer": "Reviewer_8Rq1", "summary": "This paper considers adapting a standard Transformer to work on general graphs, and applying it to a few recent graph representation learning benchmarks. They propose three ways of augmenting a standard Transformer architecture by adding new node features and additive attention biases, and show that their approach (GraphFormer) yields state-of-the-art performance on the considered benchmarks. They also prove some theoretical results stating that GraphFormer is more expressive than many standard graph neural network architectures, and conduct an ablation of the modifications they make to a standard Transformer, showing that each of them leads to better performance.\n\nAs the authors note, there has been a lot of work in adapting attention and other parts of transformers to a graph domain. In particular, there has been a lot of work on using attention mechanisms in graphs, and also more specifically in using edges to bias attention between nodes or using features based on shortest paths between nodes. Taken on their own, the modifications proposed in GraphFormer seem fairly incremental.\n\nNevertheless, most of the prior work I'm aware of focuses on individual modifications for specific tasks instead of a unified set of changes for standardized benchmark datasets, and often deviate from a standard Transformer backbone in a large number of ways. It does seem useful to demonstrate that the Transformer architecture can be applied to graph understanding tasks in a straightforward and general way, and that doing so leads to strong performance both theoretically and empirically. Transformers have shown strong results in many domains, and I think this paper could be a good starting point for future developments on using transformers for graph representation learning.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Proposed approach\nThe authors propose three ways of adapting a standard Transformer architecture to work on graphs.\n\n- First, they propose adding in-degree and out-degree embeddings to the embedding of each node, before computing the query and key attention vectors. This gives the network an ability to condition on those degrees in addition to the local features of the node itself.\n- Second, they propose computing the distance between each pair of nodes, and then using this to choose from a set of learnable biases for the attention logit between that pair of nodes. In particular, by assigning different biases, the network can learn to focus attention only on nodes in the neighborhood, or to nodes far away, with different weights assigned to each. This adjustment happens \"outside\" the key-value dot product, so it is based on distance alone and not based on the query and key embeddings.\n- Third, for graphs with edge features, they propose adding an adjustment based on the ordered sequence of edges along the shortest path between those nodes. In particular, for each possible index $n$ in the shortest path, they learn an edge weight vector ${{w^E}\\_{n}}$, then take the dot product between ${{w^E}\\_{n}}$ and the $n$-th edge feature ${{x}\\_{e\\_n}}$ along the shortest path. This is also added to the attention logits directly, allowing each attention head to learn to attend to a different type of path between nodes.\n\nIn addition to these modifications, they adapt some well-known tricks from transformers and graph neural networks:\n- They apply layer normalization before attention, which has been shown to work well for transformers in other domains,\n- They introduce a \"special\" node [VNODE] that tracks full-graph information, similar to the use of similar nodes in MPNNs and the use of the [CLS] token in BERT. However, they emphasize that this node is \"virtual\" and doesn't participate in the shortest-path embeddings (it instead gets its own, separate attention bias).\n\nOne question I had about the edge feature path embedding: what do you do when there are multiple paths of the same length? Should all of them be averaged together, or do you just pick one? (Does it matter?)\n\n## Theoretical and empirical results\nTheoretically, the authors argue that GraphFormer is able to represent the same operations as a standard GNN: in particular, that it can mask attention to the nearest neighbors, use the known degree to compute sums over neighbors, and use the FFN in the attention layer to combine node and neighbor features. Their proof defers to the universal approximation theorem of fully-connected networks, and although it is a fairly informal argument I think it's essentially correct. (I think it would be a bit more precise to say that GraphFormer can approximate any other GNN arbitrarily well with enough parameters, since that's all the universal approximation theorem allows?)\n\nThey also argue that GraphFormer is not limited by the 1-WL test, by providing an example where distances between pairs of nodes can be used to distinguish two graphs that the 1-WL test cannot distinguish. Finally, they argue that even without a special [VNODE] node, GraphFormer can still learn to aggregate information across the graph using the \"mean readout\" function (essentially, by having all of the queries, keys, and spatial biases be identical so that every node attends to every other node).\n\nEmpirically, they demonstrate their approach on the OGB Large-Scale Challenge, OGB, and benchmarking-GNN benchmarks. For each, they compare to a variety of graph neural network approaches that have been previously applied to those benchmarks. They also compare to the Graph Transformer model of Dwivedi and Bresson [13], a different general-purpose adaptation of transformers to graphs. The GraphFormer model shows strong results across the different domains, outperforming all of the reported baselines.\n\nThe authors also include an ablation study on one of the datasets, showing that each of their proposed modifications improves performance over a vanilla Transformer, as well as over some alternative encoding strategies from prior work.\n\nOne thing that would strengthen the experimental results would be to compare the GraphFormer architecture to some of the other methods for encoding paths, distances, and edge features that the authors cite in their related work section. For instance, how does GraphFormer compare to the concatenated-path-attention strategy in [9] or the distance encoding of [30]?\n\n## Originality and significance\nAs the authors note, the success of transformer-based models has led to a wide variety of work on combining parts of graph neural networks with parts of transformers. Thus, many of the ideas used in GraphFormer (in particular, using attention mechanisms locally and globally, and biasing attention using shortest paths, edge features, or distances between nodes) resemble things from prior work (and the authors do a good job of citing many of these earlier works).\n\nEven so, one of the nice things about the proposed GraphFormer architecture is that the modifications to the standard transformer architecture are quite simple and general. The node degree information is simply added as part of the node features, and the distance and path features are added as attention biases. This suggests that improvements to transformers for NLP or other domains could easily transfer to improvements in GraphFormer, and vice versa.\n\nThus, despite the simplicity of the proposed changes, I think this paper could be quite impactful by showing that, both theoretically and empirically, the standard Transformer architecture can be successfully adapted to graph representation learning tasks. In fact, the simplicity might be a good thing, as it provides a signal that the Transformer backbone can do very well with just a few extra graph-based features. I wouldn't be surprised if this was a starting point for additional research on applying transformers to graphs, even if not all of those future directions incorporate exactly the same set of modifications.\n\nOne piece of related work that the authors may be unaware of is [\"Global relational models of source code\" (Hellendoorn et al. 2019)](https://openreview.net/forum?id=B1lnbRNtwr), which proposes adding edge-feature-based attention biases to a standard transformer, applied to a graph representation of a program. \n\n## Clarity\nOverall I found the paper easy to read and well motivated. The authors provide an intuitive explanation for why each of their modifications is sensible, and give a nice proof sketch in the main text of how the GraphFormer architecture generalizes other GNN architectures.\n\nMinor suggestions for clarification:\n- Line 253: \"transferable capability of the pre-trained GraphFormer on OGB-LSC\": I initially interpreted this as transferring from something else to OGB-LSC. But I think you actually mean transferring from OGB-LSC to graph classification? Perhaps you could reword this to \"transferable capability of a GraphFormer model pre-trained on OGB-LSC\" or something similar?\n- Line 262: Is PCQM4M-LSC the same dataset you pretrain GraphFormer on, or did you pretrain on a different dataset?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is a methodological contribution without any specific negative societal impacts that I'm aware of.\n\nThe authors discuss some limitations of their work, in particular the quadratic complexity of global self attention and the need for future work on graph subsampling strategies. They also mention that their approach may be more prone to overfitting, although regularization seems to fix this. (The checklist mentions section 5 containing limitations, but I think the authors may have meant section 6?)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "IKKiD7CwHi0", "reviewer": "Reviewer_rR8v", "summary": "The paper proposed a simple Transformer-based neural network architecture for graph data, called GraphFormer. Inspired by the positional encoding in NLP, GraphFormer encodes the structural information of the graph into the Transformer architecture via 1) centrality encoding, which incorporates degree information in computing the node embeddings, 2) spatial and edge encoding, which utilizes the shortest path between nodes to determine the edge biases in self-attention. In addition, the author added a set of virtual nodes to GraphFormer that connects to all nodes via \"virtual\" edges. The author compared GraphFormer with other models in several molecule/chemistry graph classification tasks and show that GraphFormer significantly outperforms the other methods, including several SOTA Message-Passing Graph Neural Network (MPGNN) models.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n- Originality\nThe architecture of the paper is similar to the Code Transformer model proposed in [ICLR2021, Language-Agnostic Representation Learning of Source Code from Structure and Context]. However, the author has not mentioned this paper in the related work. Other than that, the usage of virtual nodes and the way of generating the edge encodings via shortest path are novel and original.\n\n- Technical Quality\nThe author performed extensive experimental evaluations of GraphFormer on benchmarks like OGB and ZINC and demonstrated that it achieves state-of-the-art performance. However, from Table 1,2,3, we can notice that GraphFormer has significantly more parameters than the baselines. This means that GraphFormer can be much more computationally expensive than the other models. Thus, it is not clear if the performance improvement of GraphFormer is attributed to its larger model size or architectural advances. In addition, one limitation of the encoding mechanism adopted by GraphFormer is that it may not be efficient for graphs with \"hubs\" (nodes with very large degrees). The author may need to mention this limitation in the paper.\n\n- Clarity\nThe paper is well-written and easy to understand.\n\n- Significance\nPerformance of GraphFormer is significantly better than the baselines according to Table 1,2,3. However, I need to see more evidence to understand if it is simply attributed to scaling up the model size or due to the usage of Transformer.\n\n\n--- Post Rebuttal ---\nThe author has address my concerns and I will increase the score to accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the author needs to state that GraphFormer may not be suitable for large graphs due to the full-attention. In addition, the author needs to emphasize on the more extensive computational cost of the model.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No concern.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}, {"review_id": "EaCpKsIZjzk", "reviewer": "Reviewer_uohB", "summary": "This work proposes a transformer architecture suited for graph representation. More precisely, the structure of the graph is encoded via three different mechanisms focused on the degrees, the distance of the shortest path between two nodes, and the edges. The resulting model outperforms different GNNs on four molecular graph tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As GNNs are the current preferred architecture for graph representations, outperforming these make this work significant. The paper is also sound and clear. Some more experiments may be useful to better understand the capabilities of GraphFormer as well as some clarifications on the novelty of the encoding mechanisms.\n\nPros:\n- The proposed architecture seems sound and simple.\n- GraphFormer obtains excellent results on OGB.\n\nCons:\n- The paper claims that the proposed Spatial Encoding is novel (l129). In my opinion, this may be exaggerated as this encoding seems rather be an instance of relative position encoding, where a parameter depending on the distance (of the shortest path) between two nodes are learned. \n- The paper does not propose experiments on smaller molecular data sets (a few hundreds/thousands graphs). This could be useful to understand how does GraphFormer do with respect to GNNs in different settings. To my understanding, these experiments could be conducted with and without pre-training.\n\nQuestions and remarks:\n- l18: what do you mean by \"powerful\"?\n- Experiments: GAT, which also applies attention (although on neighboring nodes only) could be an interesting baseline for this work, why not comparing to it?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors identify sensible limitations in their work. Negative societal impact are not mentioned, although they remain limited.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "1FHMgeN8NRF", "reviewer": "Reviewer_3WSK", "summary": "GraphFormer modifies the attention layer in a Transformer in a way to incorporate information about the structure of the graph. The modifications are intuitively motivated and show that GraphFormer is at least as powerful as GNNs. The experimental results are positive although they seem to come at the cost of many more parameters.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The idea appears to motivated by Graph Transformer and several other papers that add structural encodings to GNNs as mentioned in the Related Work section. Adding structural encodings to the attention mechanism indeed appears novel.\n\nQuality: Simple proofs are provided to show that the model is at least as powerful as GNNs. Experiments are run on Open Graph Benchmark (OGB) which is standard for deep learning on graphs. Results are strong. Ablations are done to show the importance of each structural encoding ingredient.\n\nClarity: Background knowledge is clear and diagrams are good. Information is provided to reproduce experiments.\n\nSignificance: The method is easy to apply to any graph, and the experimental results are strong. Given the familiarity of Transformers, I expect many researchers and partitioners will reach for this model when presented with graph data. The main limitation appears to be the quadratic scaling with the size of the graph.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential negative societal impact.\n\nThe authors state that performance, especially on large graphs, will limit applicability of their system.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a set of simple modifications to the popular transformer architecture so that they can work well on graph structured data.  The paper is quite clear and well-written.  Extensive empirical results show that these architectures can outperform graph neural networks on a wide range of benchmarks.

All reviewers consistently recommend accepting this paper, and are optimistic about the adoption of the proposed techniques due to their simplicity and strong empirical results.

The authors should consider the reviewers’ suggestions to improve the paper, in particular the additional related works mentioned in the reviews that can better help put this work into context.
Decision: Accept (Poster)