Deformable Graph Transformer
Authors: Jinyoung Park
Seongjun Yun
Hyeonjin Park
Jaewoo Kang
Jisu Jeong
Kyung-Min Kim
Jung-Woo Ha
Hyunwoo J. Kim
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Transformer
Graph Neural Networks

Abstract: Transformer-based models have recently shown success in representation learning on graph-structured data beyond natural language processing and computer vision. However, the success is limited to small-scale graphs due to the drawbacks of full dot-product attention on graphs such as the quadratic complexity with respect to the number of nodes and message aggregation from enormous irrelevant nodes. To address these issues, we propose Deformable Graph Transformer (DGT) that performs sparse attention via dynamically sampled relevant nodes for efficiently handling large-scale graphs with a linear complexity in the number of nodes. Specifically, our framework first constructs multiple node sequences with various criteria to consider both structural and semantic proximity. Then, combining with our learnable Katz Positional Encodings, the sparse attention is applied to the node sequences for learning node representations with a significantly reduced computational cost. Extensive experiments demonstrate that our DGT achieves state-of-the-art performance on 7 graph benchmark datasets with 2.5 ∼ 449 times less computational cost compared to transformer-based graph models with full attention.

Under review as a conference paper at ICLR 2023
DEFORMABLE GRAPH TRANSFORMER
Anonymous authors Paper under double-blind review
ABSTRACT
Transformer-basedd models have recently shown success in representation learn- ing on graph-structured data beyond natural language processing and computer vision. However, the success is limited to small-scale graphs due to the draw- backs of full dot-product attention on graphs such as the quadratic complexity with respect to the number of nodes and message aggregation from enormous irrelevant nodes. To address these issues, we propose Deformable Graph Trans- former (DGT) that performs sparse attention via dynamically selected relevant nodes for efficiently handling large-scale graphs with linear complexity in the number of nodes. Specifically, our framework first constructs multiple node se- quences with various criteria to consider both structural and semantic proximity. Then, combining with our learnable Katz Positional Encodings, the sparse atten- tion is applied to the node sequences for learning node representations with significantly reduced computational cost. Extensive experiments demonstrate that our DGT achieves superior performance on 7 graph benchmark datasets with 2.5 ~ 449 times less computational cost compared to transformer-baseee graph models with full attention.
INTRODUCTION
Transformer (Vaswani et al. 2017) has proven its effectiveness in modeling sequential data in vari-
ous tasks such natural language understanding (Devlin et al. [2019]
Yang et al. 2019: Brown al.,
2020) and speech recognition (Zhang et al.) 2020
Gulati et al.
2020 Beyond sequential data, recent
works (Dosovitskiy et al.) [021] Liu al. 2021 Yang et al.
2021
Carion et al.) 2020 Zhu al.)
2021 Zhao et al. 2 have successfully generaling gederalized ized
Transformer to various computer Vision tasks
such as image classification (Dosovitskiy et al. 2021 Liu et al. 2021 Yang et al. 2021), object
detection (Carion et al. 2020 Zhu et al. 2021 Song et 20211) and 3D shape classificatio
(Zhao
(ct al., 2021). Inspired by the success of Transformer-
models, there have been recent efforts to apply the Transformer to graph domains by using graph structural information through structural
encodings (Ying et al. 2021; Dwivedi & Bresson 2020; Mialon et al. 2021 Kreuzer et al. 2021
and they have achieved the best performance various graph-related tasks.
However, most existing Transformer- based graph models have difficulty in learning representations on large-scale graphs while they have shown their superiority on small-scale graphs. Since the Transformer- based graph models perform self-attention by treating each input node as an input to- ken, the computational cost quadratic in the number of input nodes, which is problematic on large-scale graphs. In addition, different from graph neural networks that aggregate messages from local neighborhoods, Transformer-baie ous nodes. So, on large-scale graphs, huge number of messages from falsely correlated nodes often overwhelm the information from relevant nodes. As a result, Transformer-biit based graph models often exhibit poor generalization performance. A simple method to address these issues is per- forming masked attention where the key and value pairs are restricted to neighborhoods of query nodes (Dwivedi & Bresson 2020). But, since the masked attention has a fixed small receptive field, it struggles to learn representations on large-scale graphs that require a large receptive field.
graph models globally aggregate messages from numer-
In this paper, we propose novel Transformer for graphs named Deformable Graph Trans- former (DGT) that performs sparse attention with a small set of key and value pairs adaptively selected considering both semantic and structural proximity. To be specific, our approach first gen- crates multiple node sequences for each query node with diverse sorting criteria such as Personalized PageRank (PPR) score, BFS, and feature similarity. Then, our Deformable Graph Attention (DGA),

---

Under review as a conference paper at ICLR 2023
key module of DGT, dynamically adjusts offsets to choose the key and value pairs on the gen- erated node sequences and learns representations with selected key-value pairs. In addition, we present simple and effective positional encodings to capture structural information. Motivated by Katz. index (Katz 1953). which is used for measuring connectivity between nodes, we design Katz Positional Encoding (Katz. PE) to incorporate structural similarity and distance between nodes graph into the attention. Our extensive experiments show that DGT achieved good performances on benchmark datasets and outperformed existing Transformer- bbased graph models on all datasets at significantly reduced computational cost.
Our contributions are as follows: (1) We propose Deformable Graph Transformer (DGT) that per- forms sparse attention with a reduced number of keys and values for learning node representations, which significantly improves the scalability and expressive power of Transformer-basee graph mod- els. (2) We design deformable attention for graph-structured data, Deformable Graph Attention (DGA), that flexibly attends to a small set of relevant nodes based on various types of the prox- imity between nodes. (3) We present learnable positional encodings named Katz PE to improve graph models by incorporating structural similarity and distance between nodes based on Katz index (Katz, 1953). (4) We validate the effectiveness of the Deformable Graph Transformer with extensive experimental results that our DGT achieves the best performance on 7 graph benchmark datasets with 2.5 ~ 449 times less computational cost compared to transformer-basee graph models with full attention.
the expressive power of Transformer-base
RELATED WORKS
Graph Neural Networks. Graph Neural Networks have become the de facto standard approaches
on various graph-related tasks (Kipf& & Welling 2017: Hamilton et al.] 2017 Wu et al. 2019; Xu
cct al., 2018; Gilmer et al. 2017). There have been several works that apply attention mechanisms
to graph neural networks (Rong al.) 2020 Veličković et al., 2018 Brody et al. 2022 Kim & Oh,
2021 motivated by the success of the attention. GAT (Veličković et al. 2018) and GATv2 (Brody
et al. 2022) adaptively aggregate messages from neighborhoods with the attention scheme. How- ever, the previous works often show poor performance on heterophilic graphs due to their homophily assumption that nodes within small neighborhood have similar attributes and potentially the same labels. So, recent works (Abu-El-He El-Haija et al. 2019 Pei et al.) 2020 Zhu et al., 2020: Park et al.) 2022) have been proposed to extended message aggregation beyond a few-hop neighborhood cope with both homophilic and heterophilic graphs. H2GCN (Zhu et al.) 2020) separates input features and aggregated features to preserve information of input features. Deformable GCN (Park et al., 2022 improves the flexibility of convolution by performing deformable convolution.
Transformer- Graph Models. Recently, (Ying al. 2021 Dwivedi & Bresson 2020 Mi-
alon et al.] 2021 Kreuzer et al. 2021 Wu et al. 202 have adopted the Transformer architecture for learning on graphs. Graphormer (Ying et al.) 202T) and GT (Dwivedi & Bresson, 2020) are built upon the standard Transformer architectures by incorporating structural information of graphs into the dro-product self-attention. However, these approaches, which we will refer to as 'graph Transformers' for brevity, not suitable for large-scale graphs. It is because referencing numerous key nodes for each query node is prohibitively costly, and that hinders the attention module from learning the proper function due to the noisy features from irrelevant nodes. Although restricting the attention scope to local neighbors is a simple remedy to reduce the computational complexity, it leads failure in capturing local-range dependency, which is crucial for large-scale or het- erophilic graphs. To mitigate the shortcomings of existing Transformer-ban propose DGT equipped with deformable sparse attention that dynamically selected relevant nodes to efficiently learn powerful representations on both homophilic and heterophilic graphs with signif- icantly improved scalability.
graph models, we
Sparse Transformers in Other Domains. Transformer (Vaswani et al., 2017) and its variants have achieved performance improvements in various domains such as natural language processing (De- vlin et al. 2019 Brown et al. 2020 and computer vision (Dosovitskiy et al. 202 Carion et al. 2020). However, these models require quadratic space and time complexity, which is especially problematic with long input sequences. Recent works (Choromanski et al.) 2021 Jaegle al. 2021 Kitaev et al.) (2200) have studied this issue and proposed various efficient Transformer architectures. Xiong et al. 2021) study the low-rank approximation for attention to
[Choromanski et al. 2021
2

---

Under review as a conference paper at ICLR 2023
reduce the complexity. Perceiver (Jegle et al., 2021 2022) leverages cross-attention mechanism to iteratively distill inputs into latent vectors to scale linearly with the input size. Sparse Trans- former (Child et al. 2019) uses pre-defined sparse attention patterns on keys by restricting the atten- tion pattern to be fixed local windows. (Zhu et al. (021) also proposes sparse attention that dynami- cally samples set of key/value pairs for each query without fixed attention pattern. Inspired by the deformable attention (Zhu et al. 2021), we propose deformable attention for graph-structured data that flexibly attends informative key nodes considering various types of the proximity between nodes via multiple node sequences and our learnable Katz Positional Encondings.
3
METHODS
The goal of our architecture address the limitations of Transformer-basee graph models and gen- eralize Transformers large-scale graphs. Specifically, existing Transformer-based graph models suffer from multiple challenges: 1) scalability issue caused by the quadratic computational cost in regards to the number of nodes and 2) aggregation of distracting information since enormous number of nodes are aggregated. To address the challenges, we propose Deformable Graph Trans- former (DGT). Our framework is composed of two main components: 1) deformable attention that attends to only small set of adaptively selected key nodes considering diverse relations between nodes, and 2) positional encoding that captures structural similarity and distance between nodes. Be- fore introducing our proposed architectures, we revisit the basic concepts of graph neural networks and attention in Transformers.
3.1 PRELIMINARIES
Graph Neural Networks (GNNs). Consider an undirected graph G = E) with a set of N and a set of edges V/ U/ V are connected. Each node v/ E V has feature vector x; R F. where F is the dimensionality of the node feature, and set of neighborhoods (i) {uz E Vl(u,, E E}.
.......,yy nodes {w1, .2,...., UN
{(1), 1;) 0, fy V) where the nodes
Given graph G and of node features (x, {x,),=1- Graph Neural Networks (GNNs) aim to learn each node representation by an iterative aggregation of transformed representations of the node itself and its neighborhoods as follows:
w())
h
Σ
where h1!9 E Bd is a hidden representation of node in the 1-th GNN layer, h(0) w Rud x1 is learnable weight matrix at the I-th GNN layer, a non-linear activation function, Og and Cu represent weights for aggregation characterized by each GNN. For example, GCN Kipf Welling (017)) can be represented as a form of [1) if Ca = (deg(i) (j) 1/2 and Cai (deg(i)) where deg(i) is the degree of node Us and GAT Veličković et al. (0118) learns and a
(1) based on the attention mechanism.
Attention in Transformer. Transformers Vaswani al. 2017 have shown their superior per- formance based on multi-head self attention mechanisms. Given a query index q E Ω2 with ={fe]ken,- where Sl. O2 are the
corresponding vector zg E Re and set of key/value vectors F set of query and key indices, the Multi-Hes Head Attention (MHA) is formulated as follows:
M
MHA (Z.g F)
=
W
m
Σ Amgk LkE
W fe
m
where m is the index of M attention heads, W E Rexe, and W m E Re are weight matrix parameters. The attention weight mmyk between the query Zy Re and the key fş RR, which
generally calculated as Amgk = exp U V where Z E R a normalization factor to achieve Σ Ee Amgx and U m, V tively. Although the multi-head attention operation contributes to the success of the Transformer- based models, has known issue of substantial computational costs and large memory.
Z
weight matrices to compute queries and keys. respec-
3

---

Under review as a conference paper at ICLR 2023
Sorting nodes
Kemel-bused interpolation >
Aggregating values
S PEREE
Linear
PPR
S
head
hend
Output
AGG
BFS
Input Graph
Sampling offsets
Attention weights
Feature similarity
Apmmgk
Amggg
Softmax
Preprocess
Linear
Linear
Learnable
Query node feature
Overview of the deformable graph attention module. In the pre-processing phase. NodeS- ort module first constructs multiple node sequences {r depending on query node ey by sorting nodes through diverse criteria E II. Then, the kernel-based interpolation applied on each offset to get values, whose offsets are computed by the queries with a linear projection. The deformable graph attention module aggregates the values of each head with attention weights to generate output.
Figure 1:
This scalability issue has been extensively studied in the literature. However, most efficient atten- tion methods have been developed by either limiting the attention within a local neighborhood or approximating an attention map with a low-rank matrix. The former approaches are problematic when neighbors belong to different classes as heterophilic graphs, and the latter approaches tend to yield dense attention leading to enormous messages from irrelevant nodes. So. we adopt more flexible and efficient Deformable Attention Zhu et al. (2021) Xia et al. (2022) that performs a sparse attention by dynamically sampling small set of relevant keys without predefined window.
Let E R be an input feature map and P, be position of query Zg. Then, the DeFormable Attention (DFA) defined as
M
K Σ
DFA (Z.. Pg. F
W m
Amgk: W f (Py + APmpt)
(3)
7=
where ls is an index of sampled key vectors, and K is the total number of the key. The attention weight Amgk of m-th attention head has a value between 0 and 1, normalized by > Amag
similar to the multi-head attention. Apmgk key of the m-th attention head. Since the deformable attention module uses only a small set of informative keys for each query, it has linear complexity in the number of inputs.
m, is sampling offset of the k-th sampling
In recent, Transformer- bassed models Ying et al. 2021 Dwivedi Bresson (2020) have been pro- posed to harness the power of the standard multi-head attention for representing nodes in graphs. Although they have shown superior performance on various tasks, they have difficulty learning representations large-scale graphs. Since the large-scale graph has a vast number of nodes, the scalability issue of the multi-head attention is dramatically exacerbated. Also, the enormous num- ber of keys to attend per query node increases the risk of the aggregation of noisy information from irrelevant key nodes. In this paper, we design sparse attention module, Deformable Graph At- tention, that attends only a small number of relevant keys different from standard attention that blindly aggregates irrelevant key nodes. By reducing the number of key nodes, it is possible to make transformer- based architecture effective and efficient on large-scale graphs.
3.2 DEFORMABLE GRAPH ATTENTION
In this section, present Deformable Graph Attention (DGA), key module in our proposed De- formable Graph Transformer (DGT). The overview the deformable graph attention illustrated in Figure [
The general idea of deformable graph attention to design the deformable attention
4

---

Under review as a conference paper at ICLR 2023
mechanism for graph-structured data, and therefore DGT performs the attention mechanism with partially selected relevant key nodes, which makes the wransformer-baee architecture efficient and effective on large-scale graphs. However, extending the deformable attention mechanism to graph representation learning is non-trivial since the offset-based interpolation in the deformable attention only works in Euclidean space whereas graphs are non-Ruclidean data. Also, even when embed- ding nodes in graph into a low-dimensional space via graph embedding methods (e.g., Node2vec (Grover & Leskovec 2016)), nodes are irregularly distributed in the low-dimensional space, which makes difficult to effectively deform an attention map.
To address this challenge, we propose NodeSort module that converts a graph into a sorted se- quence of nodes in regular space. We define base node as the first node in sorted sequence which is similar to an ego node an ego graph. NodeSort differentially sorts nodes depending on the base node. In other words, NodeSort provides a relative ordering that varies across base nodes whereas conventional topological sort yields a single (absolute) ordering for graph. Specifically, given a base node, NodeSort sorts nodes and returns sequence of their features as follows:
Sb = (9 tb, (x:)==)) = [ (t))))))
(4)
where π denotes a specific criterion for sorting nodes and aub is bijective mapping from V to V depending on a base node vg. To consider both structural and semantic proximity, we generate multiple sorted node sequences for each node Vb. fell from set of diverse criteria II. such as Personalized PageRank (PPR) score, BFS, and feature similarity. More details the NodeSort module and criteria are in Section B.2 Note that dr redefines neighbors of each node Ub based on various aspects II beyond 1 1-hop neighbors in the existing GNNs.
Now, we introduce our Deformable Graph Attention (DGA), which is a sparse attention by dynam- ically sampling key/value pairs from the set of sorted sequences of node features. To benefit from various properties of the graphs, the deformable graph attention module is designed to deal with diverse node sequences. Different from existing methods based on deformable sampling modules in computer vision, which only considers spatial proximity on a grid, DGA captures both structural and semantic proximity. Given the set of sorted sequences { TELI and features of query node Z, DGA is defined as
M
K mm Σ
DGA (zg: (5gg)en))
W
Amgk Lk=1
W mm Sag (Aprmgk)
(5)
TEIl m===
where Sag (Apamgh) denotes the representation of the k-th key, K denotes the number of keys, W Wxm Rexos and W Wim Re are the learnable weight matrices for each criteria π E II and the m-th attention head, Axmek = 8 (zy) denotes the attention weight from linear function gat between the g-th query and the k-th key of the m-th attention head and criterion n, which normalized by >K Anmgk = and the attention weight needs to in a interval [0. 1].
Apamgk is sampling offset of the k-th key for criterion and m-th attention head, which is generated by gett (Ry). where golt is linear function with an activation function. As the offset Apamgk is fractional, we compute 3.,, (p) by kernel-based interpolation:
g(a,b) = exp (- [a- [a-b))))) if a - bl <
Bay (p) Eg(p. S.gli,
(6)
1,
otherwise
where ? E +++ denotes the bandwidth of the kernel, c is a hyper-parameter for truncating the kernel, and S [i is the node feature at i-th index of the sequence Szq.
A standard way of computing 3xg (p) is calculating Eq. ( by substituting with (a, b) max (0, a - bl). But, the existing way considers only two nodes whose coordinates are ceiling and floor values of point p. It might not be sufficient for the offsets Ap move to get relevant information by looking at only two nodes. As the scale of the graph increases, a target node requires much more nodes learn its representation. So, we apply the Radial Basis Function kernel for computing Srg as in Eq. d look a wide range of nodes for representing query nodes.
5

---

Under review as a conference paper at ICLR 2023
3.3 KATZ POSITIONAL ENCODING
Positional Encoding is a crucial component in Transformer to reflect domain-specific positional information into its attention mechanism. A major issue with positional encoding graphs is the absence of absolute positions of nodes, unlike other domains. One remedy to this issue is to encode relations between nodes. Here, we propose learnable positional encodings, Katz PE, for mannsformer-basee graph models based on connectivity between nodes. To be specific, inspired by the matrix of Katz indices (Katz) 1953) which counts all paths between nodes with the decaying weight 3 reflect the preference for shorter paths, i.e., A = Σx=1 Bk A* our method learns positional embeddings, PE,, of each node by the nonlinear transform of A as follows:
Katz (E(e:) = MLP(A((:)²),
where MLP is a Multi-Layer Perceptron, and A [v:] is the row vector node v; Å. We limit the k= Ex= g AA for the efficient calculation. In addition, when
maximum k in A to K, i.e., A N large, then we sample N' anchor nodes with high degree and utilize the submatrix of Katz indices A' NN*,", Our learnable Katz PE is simple yet more effective for both our DGT and vanilla Transformer than existing pre-computed positional encodings. See Section for more details.
3.4 DEFORMABLE GRAPH TRANSFORMER
Finally, we introduce our Deformable Graph Transformer (DGT) built upon our proposed Graph Deformable Attention and Positional Encoding. Deformable Graph Transformer first encodes node feature x, with the learnable function fo. which can be MLP, and combines with positional embed- dings from Eq. as
(0) = fo(;)) + Katz PE(e:).
Then, given a set of sorted sequences { hen from Eq. (5. each (-th Deformable Graph Attention layer in DGT performs the attention mechanism with small set of informative keys and applies skip-connection and MLP to update node representations as follows:
2(") DGA (S z"-1)) ((=1))+2"+1 z -MLP(2 +2
(L) is After the stack of L Deformable Graph Attention blocks, each node representation z; used for node classification on top and MLP followed by a softmax layer used as ÿi Soltmax(MLP(2, Our loss function is a cross-entropy on nodes that have ground truth labels.
3.5 COMPLEXITY ANALYSIS
We provide the comparison of computational complexity between the self-attention in most Transformer-basee graph models and the Deformable Graph Attention (DGA) in our DGT. As the number of nodes N increases, our DGA with a linear complexity of N more efficient than the self-attention with quadratic complexity of N. The details are in Sec A
4 EXPERIMENTS
In this section, we evaluate the effectiveness of our proposed Deformable Graph Transformer (DGT) against state-of-the-ar models on node classification benchmark datasets.
4.1 EXPERIMENTAL SETUP
Datasets. We validate the effectiveness of our model node classification using four heterophilic graph datasets and four homophilic graph datasets, which are distinguished by the edge-based ho- mophily ratio /huu et al. 2020) defined as h based homophily ratio ranged from h 0.22 (very heterophilic) to h 0.81 (very homophilic). For large-scale graphs, we evaluate our method on twitch-gae twitch-gamers, obgn-arxiv, and Reddit datasets. More details about the datasets are in Sec F.
(E [8]
Each dataset has an edge-

---

Under review as a conference paper at ICLR 2023
Table 1: Evaluation results node classification task (Mean accuracy (%) + 95% confidence in- terval), OOM denotes 'out-of-memory' Bold indicates the model with the best performance and underline indicates the second best model.
twitch- gamers
Avg. Rank
Model
Actor
Squirel
Chameleon
Cora
Citescer
ogbn-arxiv
Reddit
Nodes
7,600
5,201
2,277
2,708
3,327
168, 114
169,343
232,965
# Edges
26,659
198,353
31,371
5,278
4,552
6,797,557
1,166,243
11,606,919
Hom. ratio
0.22
0.22
0.23
0.81
0.74
0.55
0.66
0.76
GNN-based Models
MLP
35.05
31.66+032
40.1
75. 10=004
73.54=000
61.1420.8
53.89
10.03+a.16
12.38
GCN
30.13+0.30 50.42+066
66.33+064
87
76.08=043
64.3446.12
71.27+0.11
95,06+m0a
7.25
GAT
30.25+0.39
54.26+1.1
66.85
=6.21
75.71=0.2
62.90=0.22
70.92+0.11
OOM
9.13
GraphSAGE
35.24:0049
43.751075
63.28
86.94
76.25
64.7310.11
10.1910.11
96,271001
7.13
JKNet
30.3910.35
57.00.2022
67.81 1::6
87.17
76.33.2053
65.08
71.0010.15
95.281002
6.25
SGC
29.4310.11
35.07:051
49.95
87.33
39
75.47:2056
60.47:00.4
66.562201
94.72:1000
11.25
GATv2
30.5422.41
5794
67.25
86,
41
75.63:2049
64.1520000
71.01
OOM
8.25
MixHop
35.79
38.78:006
59.27
87.16
=5.95
65.20=0.12
71.47.0.15
96.234u044
6.25
Geom-GCN
31.5310.31
37.98
60.70
20.3
76.57.00.5
N/A
N/A
N/A
10.50
H2GCN
35.3210.34
36.891080
58.21
87.73
76.88
OOM
OOM
OOM
8.50
DefomableGCN
36.5310.22
62.09
11.0
87.32.10.4
76.67.1043
OOM
70.22.0.19
OOM
6.00
Trunsformer-based Graph Models
Transformer
36.61
31,0010.0
45.93
73.75
72.99
OOM
OOM
OOM
12.63
Graphormer
36.5410.4
36.251072
50.15:126
73.44.000
23.60
OOM
OOM
OOM
12.00
GT-full
34.5310.8
32.33:104
49.07
69.51
70.
70.18:200 18:087
0OM
0OM
OOM
13.63
GT-sparse
34.69:.0.35
44.22
64.82+a0.7
85.63
=5.49
63.09
71.45
OOM
8.75
DGTT-lggh (Ours)
36.86.0.53
62,58
:3.04
86.60=0060
75.72:00.0
65.59
71. 71.18
96.1 16
4.38
DGT (Ours)
36.93
63.78.0059
73.48
87.5
9.50
71.77 66.09...23
96.32 1.002
1.13
Table 2: Efficiency comparisons on Transformer-based graph models. measured by CPU implementation.
denotes the performance
Chameleon
Cora
Citeszer
Squirell
twisch-gamers
oghn-arkiv
Nodes
2,277
2,708
3,327
5,201
168.114
169,343
Edges
31,371
5,278
6,797557
1.166,243
Model
FLOIS
Acc.
FLOPS
Acc.
FLOP
FLOPs
Transformer
100G
45:93a243
1,266
73.75
2.29G
72.99
4,29G
31.00.00
3022G"
59.851
GOM
OOM
Graphormer
1.8G
50.15:: x
2.36G
73.44
3.79G
72.602203
7.88G
36.25
00M
GOM
G0M
GT-full
1.7G
49.07a::5
1,27G
69.51
231GG
70.18
4.31G
32.33
3623G"
59.18!
00M
00M
GT-spuse
6.43G
61.82s137
0.43G
85.63as4
0.99G
75.49
1.49G
44.22
17.04G
63.09
20.24G
71,45
DGT--light (Ours)
6.43G
73.04:345
0,36G
36.6000.00
0.87G
75.72
1.24G
62.58
8.05G
63.39
5,02G
71.18011
DGT (Ours)
0
13
0.65G
87.55
1.05G
77.04:057
2,63G
63.78:
16.19G
66.09.a2:
6.666
71.77
Baselines.
To demonstrate the effectiveness of our Deformable Graph Transformer (DGT), we
compare DGT with following baselines: (1) six standard GNNs: GCN (Kipf Welling 2017
GAT (Veličković et al.] 2018). GraphSAGE (Hamilton et al.] (017). JKNet (Xu et al." 2018
SGC (Wu et al. 2019). GATv2 (Brody et al. 2022); (2) four GNNs designed for heterophilic set-
tings: MixHop (Abu-El-Haija
al. 2019). Geom-GCN (Pei et al. 2020). H2GCN (Zhu et al.)
2020). DeformableGCN (Park et al. 2022): ; (3) four Transformer- based architectures for graphs: Transformer (Vaswani al. (2017). Graphormer (Ying et al. 2021I. GT-full (Dwivedi & Bresson 2020). GT-sparse (Dwivedi & Bresson 2020). (4) two variants of our proposed DGT: DIGT-light
using a single sorting criterion (II: BFS) and DGT using multiple sorting criteria [IT 3).
4.2 EXPERIMENTAL RESULTS
Table I summarizes node classification results of our proposed DGT and DGT-light, GNN-based models, and Transformer-basee based graph models. DGT consistently shows superior performance across all eight datasets. Especially, our DGT significantly outperforms transformer based baselines by a large margin up 106%. Surprisingly, existing Transformer-basee formance compared to GNN baselines except for Actor. This implies that Transformer- based graph models failed to filter out irreeevant messages and focus useful nodes. In addition, they not
graph models show poor per-
7

---

Under review as a conference paper at ICLR 2023
Table 3: Performance comparisons different ordering and criteria for constructing node
quences.
Name
Ordering
Criteria (r)
Cora
Citeseer
Chameleon
Squirrel
AR
Absolute
Random
1..5
72.27:00.2
70.51
62.44
AB
Absolute
BFS
81.22=1.14
72.28+0.69
71.95=0049
62.3
AM
Absolute
Fes.
83.28=0077
70.20+10.4
72.41 ::0.5
62.28
RB
Relative
BFS
86.60=0.00
75.72++0.40
73.04+0065
62.58+0057
RM
Relative
BFS,PPR,Featt
87.55=
77.04
73.48
63.78
Table 4: Effects of different positional encodings.
Model
Positional Encoding
Cora
Citeseer
Chameleon
Squirrel
Transformer
w/o
73.75=071
72.99+0.61
45.93=083
31.00=00.0
Node2Vec
81.52:00.8
72.07 10..8
49.00
39.15
Laplacian Figvecs
11.01
70. 10.667
49.07 1:25
32.33
RWPE
79.46=00.5
1..94
53.81 20665
40.82:+0..8
Katz PE (ours)
81.44
73.02
72.13 00.60
59.79:+0.76
DGT (ours)
w/o PE
86.32=0.52
76.61 #0.61
59.44=0087
46.59
Node2Vec
86.80=0.51
75.3640.54
62.02
50,26
Laplacian Eigvecs
83. 00.677
76,21
58.02=0091
43. 13.86+00.67
RWPE
87. $7.08 00.60
76. 1:0.56
61.48 0.83
49.56::0.67
Katz PE (ours)
87.55
77.04
1..4
63.78.:0.59
applicable to large-scale graphs such ogbn-arxiv, twitch-gamers, and Reddit due to their huge computational costs.
On the other hand, our DGT consistently outperforms both GNNs and Transformer-based graph models on almost all datasets and efficiently handles large-scale graphs by utilizing small set of relevant nodes. GNNs generally perform well in homophilic graphs such as Cora and Citeseer, but show relatively inferior performance in heterophilic graphs such as Actor, Squirrel, Chameleon, and twitch-gamers. This is because most GNNs utilize directly connected nodes for aggregation even in heterophilic graphs. Instead, our DGT and DGT-light show larger performance gain in heterophilic graph datasets since it captures long-range dependency, which is important for learning on heterophilic graphs.
We also compare DGT and DGT-light with other Transformer-basee architectures to validate the efficiency (FLOPs) our DGT in Table 2 The table shows that our DGT and DGT-light improves not only the performance but also the efficiency with deformable graph attention on various datasets. As the number of nodes increases, the gap between Transformer and variants of DGT with respect FLOPS becomes bigger. In particular, on the twitch-gamers, DGT-light (8.05G) reduces computational costs by x 449 compared to Transformer (3622G).
4.3 QUANTITATIVE ANALYSIS
Here, we provide quantitative results of additional experiments to demonstrate the contribution of each component of our Deformable Graph Transformer. We first provide the ablation study of the NodeSort module and examine the effectiveness of our positional encoding comparing with popular positional encoding methods.
NodeSort module. We conduct ablation study of the NodeSort module to study the effect of the relative ordering that varies depending on base nodes and various sorting criteria. We compare several constructions: absolute ordering with random permutation (AR), absolute ordering with BFS (AB), absolute ordering with multiple criteria (AM), relative ordering with BES (RB), and relative ordering with multiple criteria (RM). From Table 3 the absolute ordering approaches (AR, AB, AM) show poor performance. The absolute ordering with BFS (AB) shows no performance gain compared randomly permuted absolute ordering (AR) three datasets. This shows that
8

---

Under review as a conference paper at ICLR 2023
U
U
-hop
Graphormer
(b) DGT (ours)
Figure 2: Visualization of the 20 most important key nodes for given query node by in (a) Graphormer and (b) DGT on Chameleon validation set. Red nodes denote nodes with the same label as the query node's label whereas blue nodes have different labels. Orange dashed lines repre- sent connections between the query node and key nodes with the same label as the query node and gray dashed lines represent the connections between nodes with different labels.
single absolute node sequence is not sufficient learn complex relationships between nodes. On the other hand, the relative ordering with BFS (RB) shows a significant performance improvement up 5.07 Further, the relative ordering with multiple criteria (RM) consistently shows superior performance compared to the relative ordering with BFS (RB).
Positional encoding. To validate the effectiveness of our positional encoding, we compare our proposed PE methods with models without positional encodings (w/o PE) and various encoding methods such Node2Vec (Grover & Leskovee (2016). Laplacian Eigvecs used in GT (Dwivedi) & Bresson 2020). and RWPE Dwivedi et al. (2022) on four datasets. We use Transformer and DGT for the base models. Table demonstrates that our positional encoding is effective on both base models. In particular, it improves the performance by 17.19(%) compared to DGT without positional encoding on Squirrel.
4.4 QUALITATIVE ANALYSIS
We provide qualitative analysis understand why DGT is effective. We visualize the top 20 key nodes with high attention scores for given query node Ei in Graphormer and DGT. In DGT, we compute attention scores of each node, v; by w, ΣE Arrgk g ((Axmmgk. i). As shown in Figure within I-hop neighborhood of the given query node Vg. out of neighbors have different labels. So, both DGT and Graphormer aggregate messages (dashed lines) from remote nodes beyond 1-hop neighbors through the attention mechanism. 17 of the top 20 nodes in DGT are nodes with the same label whereas only 4 out of 20 nodes have the same label in Graphormer. Also, the ratio of the attention scores for the nodes with the same label, i.e., Σ (v::: wi/ Weyee W; is 0.97 for DGT and 0.21 for Graphormer. This evidences that DGT effectively performs the sparse attention by focusing on a small set of relevant key nodes compared to Graphormer.
CONCLUSION
We propose Deformable Graph Transformer (DGT) that performs sparse attention, named De- formable Graph Attention (DGA) for learning node representations on large-scale graphs. With Deformable Graph Attention, our model can address two limitations of Transformer-based graph models such as a scalability issue and aggregation of noisy information. Different from standard deformable attention (Zhu et al. 202 Xia et al. 2022), the Deformable Graph Attention considers both structural and semantic proximity based on diverse node sequences. Also, we design simple and effective positional encodings for graph Transformers. Our extensive experiments demonstrate that DGT outperforms existing Transformer-bar graph models on eight graph datasets. We hope work paves the way for generalizing Transformers large-scale graphs.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In ICML, 2019.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In ICLR, 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. In NeurlPS, 2020.
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usumier, Alexander Kirillov, and Sergey 7agoruyko. End-to-end object detection with transformers. In ECCV, 2020.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv: 1904. 10509, 2019.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, al. Rethinking attention with performers. In ICLR, 2021.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. In AAA/workshop, 2020.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. (tt::20033009822. 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In ICLR, 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLRW, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In JCML, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, 2016.
Anmol Gulati, James Qin, Chung- Chegg- Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, et al. Conformer: annolltiionauugeette transformer for speech recognition. In Interspeech, 2020.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs In NewrIPS, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. NeurIPS, 2020.
Andrew Jaegle, Felix Gimeno, Andy Brock, Oriol Vinyals, Andrew Zisserman, and Joao Carreira. Perceiver: General perception with iterative attention. In ICMI, 2021.
Andrew Jaegle, Sebastian Borgeaud, jean-Baptiste Alayrac, Carl Doersch, Catalin lonescu, David Ding, Skanda Koppula, Daniel Zoran, Andrew Brock, Evan Shelhamer, et al. Perceiver io: A general architecture for structured inputs & outputs. In ICI.R, 2022.
10

---

Under review as a conference paper at ICLR 2023
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-43 1953.
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with self-supervision. In ICLR, 2021.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In ICLR, 2020.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Graph neural networks meet personalized pagerank. In ICLR, 2019.
Predict then propagate:
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. In NeurlPS, 2021.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. In NeurlPS, 2021.
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. In ICCV, 2021.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv:2106.0566 05667, 2021.
Jinyoung Park, Sungdong Yoo, Jihwan Park, and Hyunwoo J Kim. Deformable graph convolutional networks. In AAAI, 2022.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NeurlPSworkshop. 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. In NeurlPS, 2020.
Benedek Rozemberezki and Rik Sarkar. Twitch gamers: dataset for evaluating proximity preserv- ing and structural role-based node embeddings. arXiv:2101.03091, 2021.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Nenworks, 9())xnabb01, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rade Collective classification in network data. Al magazine, 29(3):33-93, 2008.
Hwanjun Song, Deqing Sun, Sanghyuk Chun, Varun Jampani, Dongyoon Han, Byeongho Heo, Wonjae Kim, and Ming-Hsuan Yang. Vidt: An efficient and effective fully transformer-based object detector. In International Conference on Learning Representations, 2021.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. JMLR, 15(1):1929-1958. 2014.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In SIGKDD, pp. 807-816, 2009.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurlPS, 2017.
11

---

Under review as a conference paper at ICLR 2023
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks.
(xXiv:1909.0115.3 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In ICML, 2019.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and lon Stoica. Representing long-range context for graph neural networks with global attention. In NeurlPS, 2021.
Zhuofan Xia, Xuran Pan, Shiji Song, Li Erran Li, and Gao Huang. Vision transformer with de- formable attention. In CVPR, 2022.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: nystöm-based algorithm for approximating self-attention. In AAAI, 2021.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICMI,, 2018.
Jianwei Yang, Chunyuan Li, Pengchuan Zhang, Xiyang Dai, Bin Xiao, Lu Yuan, and Jianfeng Gao.
Focal self-attention for local-global interactions in vision transformers. NeurlPS, 2021.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. In NeurIPS, 2019.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie Yan Liu. Do transformers really perform badly for graph representation? In NeurlPS, 2021.
Qian Zhang, Han Lu, Hasim Sak, Anshuman Tripathi, Erik McDermott, Stephen Koo, and Shankar Kumar. Transformer transducer: A streamable speech recognition model with transformer en- coders and rmn-t loss. In ICASSP, 2020.
Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip HS Torr, and Vladlen Koltun. Point transformer. In ICCV, 2021.
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 NeurlPS, 2020.
Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai. Deformable detr: Deformable transformers for end-to-end object detection. In ICLR, 2021.
12

---

Under review as a conference paper at ICLR 2023
A COMPLEXITY FOR DEFORMABLE GRAPH ATTENTION
Self-Attention in most Transformer-based graph models (Vaswani et al., 2017: Ying et al.) 2021; Dwivedi & Bresson, 2020). Suppose that N is the number of nodes, C' the dimensionality of hidden representations. The self-attention operation requires a huge computation cost with the complexity of O (N NC²), where C is the dimensionality of hidden representations.
Deformable Graph Attention. Consider is the number heads, is the number of keys. T the number of critera, and W is the number of nonzero values of g in Eq. (6). In the Deformable Graph Attention (Eq. (5) 5), calculating the sampling offsets Apamgt and attention weights A smgg requires the complexity of D(NCMKT) Then, given the sampling offsets and attention weights, the complexity of calculating Eq. 5 is NNCCTT+NKTTTT
N KCT), where W is the number of nonzero values of Sxy (Aprmmp)))) and the factor W is because of the kernel based interpolation.
We can calculate the linear transformation of the interpolated features W (Ap terpolation of the linear transformed features W. X. So, the complexity become C WNKCT). In the results, the overall complexity of Deformable Graph Attention O(N (C + WKCT + CMKTT)). In our implementation, we set M = 4, K and C 64 as default, thus MK < C' and the complexity of O(N (C=T +TT+WWA WKCT)) ,which a linear complexity with respect to the number of nodes N > W, W,K,C,T.
by in- calculating Eq. (5)
B ADDITIONAL EXPERIMENTS
Here, we provide additional experimental results to analyze the contributions of each component of our Deformable Graph Transformer (DGT) including the ablation study of the NodeSort module and our kernel-based interpolation.
B. NODESORT MODULE.
We conduct an ablation study for the NodeSort module to validate the effectiveness of single node sequence with each criterion and multiple node sequences. We use three criteria for sorting: Breadth-first Search (BFS), Personalized PageRank score (PPR), and Feature similarity (Feature). As shown in T5 when multiple node sequences are applied, DGT shows good performance on four datasets. In particular, on the cora dataset, multiple node sequences improve 3,46 (%) over the model with the Feature similarity criterion.
Table 5: Performance comparisons on different criteria for constructing node sequences.
Criteria
Squirrel
Chameleon
Cora
Citeseer
BFS
PPR
Feature
62.58
73.0440.6
86.60+0.60
75.72+0040
62.5740.59
72.66++0.7
86.31
75.42+1064
/
62.66+0073
72.67+080
84.09+0.62
1
/
/
63.78:+0.99
73.48
87.55++0.99
77.04
B.2 KERNEL-BASED INTERPOLATION.
In Figure 3 we conduct an ablation study of our kernel-based interpolation according to e = 1, 2, 3, 4,5, 5, 7,8 in g on the Cora dataset. The model shows the worst performance when = 1. As the value
increases, the model shows better performance. We believe that the value of e needs to be appropriately big to find out relevant nodes for query node.
We also compare the performance of bilinear interpolation used in (Zhu et al. 2021 and kemel- based interpolation in Table 6 As shown in the table, kernel-based interpolation improves learnabality of offsets compared to the bilinear interpolation.
13

---

Under review as a conference paper at ICLR 2023
Table 6: Performance comparisons different interpolation methods.
Method
Cora
Citeseer
Chameleon
Squirel
twitch-gamers
Bilinear interpolation
86.02
40.6
68.514056
61.69
63.30=0.15
Kernel-based interpolation (Ours)
87.55
77.04:0.57
63.78
73.48
66.09=0.12
Table 7: Evaluation results graph regression task.
Model
ZINC
GCN
0.367
GAT
0.384
GraphSAGE
0.398
GT-fuull
0.226
Graphormer
0.122
DGT (Ours)
0.158
B.3 EXPERIMENTAL RESULTS ON GRAPH REGRESSION TASK.
To validate the effectiveness Deformable Graph Transformer (DGT), we additionally conduct experiment graph regression task with ZINC dataset Dwivedi dwiveet al. (2020) Table Even though DGT mainly focus on node classification tasks, our DGT shows better performance compared to
GT-full, which has been proposed for dealing with graph regression/clasifccttio tasks.
Accuracy
87
86
1
2
3
4
5
6
8
Epsilon (E)
Figure 3: Analysis of our kernel-based interpolation according to e in
C DETAILS OF NODESORT MODULE
Our NodeSort module converts graph into sorted sequence of nodes to embed nodes in the regular space without using learnable parameters. The criteria indicate how to sort our nodes. We use three criteria: BFS, Personalized PageRank (PPR) score, and Feature similarity.
Breadth First Search (BFS): Breadth First Search is widely used algorithm for searching on graph-structured dataset. Given the graph and the base node, we set the base node as root node and do breadth first search to get the sequence of nodes.
Personalized PageRank score Personalized PageRank score is a score that encodes the local neighborhood for root node. We approximated personalized pagerank score Klicpera et al. (2019) for NodeSort module. Given the graph and the base node, T
calculate personalized page rank where the x is the base node. Then, we sort nodes in descending order of personalized page rank score.
(k) (i.), ((++1) (1 - a A (i.) + ampor
14

---

Under review as a conference paper at ICLR 2023
100
Figure 4: Visualization of the position of ((Pak)) (stars) in Section on sequence generated via BFS with Actor dataset. Color different according to the query node Vp--
Feature similarity We use cosine similarity to compute inout feature similarity between nodes. Given the input features of nodes and the base node, we measure the similarity score between the imput feature of base node and other nodes through the cosine similarity, Then, we sort nodes in descending order of similarity score.
BFS and PPR are used to generate node sequences based on structural similarity. In BFS, nodes with low shortest path distances from the base node are located in front of the sequence, and in PPR, nodes with high random walk scores from the base node are located in front of the sequence. Conversely, feature similarity is used for semantic proximity between nodes, and nodes with high semantic proximity to the base node are located in front of the sequence. By adopting diverse criteria for NoreSort module, deformable graph attention simultancously consider both semantic and structure proximity to design node sequences.
D COMPARISON OF KATZPE WITH RWPE
Our Katz PE is different from Random Walk Positional Encoding (RWPE) (Connectivity between two nodes under k-th hop v.s. Landing probability of node to itself on k-th hop). We clarify the difference in the below:
Random Walk Positional Encoding (RWPE) of i-th node is defined as
RWPE
RW iz RW No RW: R
(10)
where RW = AD-1 the random walk operator. So, RWPE expresses the landing probability of node i to itself on k-th hop. On the other hand, our Katz PEs are defined
KatzPE(e;)) = MLP(A[
(11)
where A = = A and it represents connectivity between nodes with the decaying weight (9 to reflect the preference of path lengths. The equations clearly show that KatzPE does NOT have D-1 and RW does NOT have g and summation.
E COMPARISON OF DGT WITH DEFORMABLE DETR
Our deformable graph attention addresses the challenges of applying deformable attention to graph- structured data. Since the deformable attention mechanism can only work on the regular space, it is not directly applicable to graph data. We address the challenge by transforming irregular space into a set of regular spaces using our NodeSort module. Our NodeSort module is novel the following aspects:
Locality Deformable attention in Deformable DETR is defined on only one global grid whereas our deformable graph attention utilizes node sequences locally defined each neighborhood (ego graph).
Multiple relations Our Deformable Graph Attention (DGA) module uses diverse criteria (e.g. bfs, feature similarity, ppr) even in neighborhood for constructing multiple node sequences to consider various relations in a graph.
Semantic space: We extended the deformable attention from a physical space to semantic space by performing NodeSort based node feature similarity.
15

---

Under review as a conference paper at ICLR 2023
We also improve learnability of offsets by replacing bilinear interpolation in deformable DETR with our kernel-basee interpolation (Eq. (6)). Although this technique is simple, it largely improves the performance shown in Table 6.
F EXPERIMENTAL DETAILS
F.1 DATASETS
We use four heterophilic graph datasets and four homophilic graph datasets for our experiments. To the best of our knowledge, all the datasets for experiments do not contain personally identifi- able information or offensive contents.
For homophilic graphs, node classification dataset (ogbn-arxiv) (uu et al. 2020). and Reddit (Hamilton et al.
two Planetoid datasets (Citeseer and Cora) (enn al.
2008 OGB
2017 Plan-
etoid and ogbn-arxiv datasets are citation networks whose nodes represent papers and edges indicate citations between papers. Node labels are the topics of each paper and node features are the bag- of-words of papers Planetoid datasets and word2vec of papers in ogbn-arxiv. Reddit dataset composed of Reddit posts and the node label is community, which post belongs to.
For heterophilic graphs, we use four graph datasets: Squirre Rozemberczki et al. 2021 Chameleon (Rozemberczki et al. al. 2021), Actor" IT (Tang et al. 22099) and twitch- twitch-gamer [Lm et al. 2021 Rozemberczki & Sarkar| 2021). Squirrel and Chameleon are web page datasets collected from Wikipedia (Rozemberczki et al. (021), where the nodes are web pages, edges are links between them, node features are keywords of the pages, and labels are five categories based on the monthly traffic of the web pages. Actor is an actor co-occurrence network, where nodes actors, edges represent co-occurrence on the same Wikipedia page, node features are keywords in the Wikipedia pages, and labels are five categories in terms of words of actor's Wikipedia. twitch-gant trrch-gammrs is online social network (Lim et al.) 2021; Rozemberezki & Sarkar (021), where nodes are Twitch users, edges are mutual follower relationships between them, and node features include number of views, creation and update dates, language, life time, and whether the account is dead. Node labels denote whether the channel has explicit content.
F.2 IMPLEMENTATION DETAILS
As written Section 4.1 in the main paper, all the models including baselines and our DGT are optimized using Adam optimizer (Kingma & Ba 2013). The experiments are conducted on single GPU (RTX 2080 or A6000). For all cases, learning rates and weight decay are optimized in the same search space: learning rate in (0.05, 0.01, 0.005), weight decay in {1e-3, 5e-4, Se-5). The hidden dimension is fixed with 64 and for all the cases. Also, the dropout (Srivastava et al,] 2014) is applied and the epochs are 1000 with patience 100 for early stopping. The best model on the validation split is used for reporting the performance. We adopt the splits (48% 32% 20%) of nodes per class for (train/ validation/ test) following (Pei al. 2020 Zhu al., 2020) and the experiments are repeated 30 times on Actor, Squirrel, Chameleon, Cora, and Citeseer datasets. For twitch-gamers, ogbn-arxiv, and Reddit, the experiments are conducted with the splits provided by Lim et al. 2021), (Hu et al. 2020), and (Hamilton et al. 2017), respectively and repeated 10 times.
Implementation details of Baselines. We implement the baselines using Pytorch Paszke et al. 2017) geometric deep learning library Torch- Brrch-Geometri 1 Fey & Lenssen (2019). and Deep Graph Library
Wang et al. (2019). The detailed experimental settings for each baseline models are in
Table
CCoyrrihtt (c) 2019 OGB Team. Licensed under MIT License
CCoyrright (c) 2007 Free Software Foundation, Inc. under GNU GENERAL PUBLIC LICENSE
CCoyrright (c) Wikipedia:Text of Creative Commons Auribution. under ShareAlike 3.0 Unported License
*Copyright (c) 2019 Benedek Rozemberczki. Licensed under MIT License
'Copyright (c) 2016 Facebook, Inc (Adam Paszke). Licensed under BSD-3-Clause License
'Copyright (c) 2020 Matthias Fey. Licensed under MIT License
Copyright (c) 2019 DGL. Licensed under Apache License, Version 2,0
16

---

Under review as a conference paper at ICLR 2023
Table 8: The hyper-parameter settings for our experiments
Model
Hyper-parameters
MLP
learning rate in {0.05, 0.01, 0.005), weight decay in {le-3, (e-4,, 5e-4, 5e-5)
learning rate in (0.05, 0.01, 0.005), weight decay in {1e-3, 5e-4, 5e-5)
GCN
layer in {1, 2, 4)
learning rate in {0.05, 0.01, 0.005}, weight decay in {le-3, 5c-4, 5e-5),
G
layer in {1. 2, 3, 4), the number of heads {1.4)
learning rate in {0.05, 0.01, 0.005). weight decay in {le-3, 5c-4, 5c-5), layer in {1, 2, 3, 4}
GraphSAGE
learning rate in {0.05, 0.01, 0.005), weight decay in {1e-3, Se-4, 5e-5), layer in {1, 2, 3)
JKNet
learning rate in {0.05, 0.01, 0.005), weight decay {le-3, 5e-4, 5c-5), K in
SGQ |
learning rate in {0.05, 0.01, 0.005), weight decay in {le-3, 5e-4, 5e-5), layer in 2, 3, 4), the number of heads in (1.4)
GATv2
13
learning rate in {0.05, 0.01, 0.005}, weight decay in {le-3, Se-4, 5c-5), layer in 2, 3, 4), and maximum value of Pis
MixHop
Geom-GCN 14
learning rate in {0.05, 0.01, 0.005). weight decay in fle-3, 5e-4, 5e-5}
learning rate in {0.05, 0.01, 0.005 } weight decay in {le-3, 5e-4, 5c-5), K in (1.2)
H2GCN
learning rate in {0.05, 0.01, 0.005). weight decay in {le-3, 5e-4, 5e-5), block in {1, 2), the number of neighbors in 15,10,,,,20,25)
DeformableGCN
learning rate in (0.05,0001.0.005), weight decay in (1e-3,5e-4.5es the number of blocks in (1,2,3), the number of heads in (1.4)
Transforme 15
learning rate in (0.05,0.01, ,0.005). weight decay in (1e-3,5e-4,5e-5),
Graphorme
the number of blocks in { (1.2.3), and the number of heads in (1,4)
learning in (0.05,0.01, (0.05,0.01,000055) weight decay in (1e-3,5e-4,5e-5),
GT-ful
the number blocks in (1,2.3), the number of heads (1.4)
learning rate in (0.05,0.01,0.000) weight decay in [Ic-3.5e-4.55c
GT-sparse
the number blocks in { (1,2.3), the number of heads in [1.4]
learning rate in {0.05, 0.01, 0.005). weight decay in {1e-3, 5e-4, 5e-5),
DGT-light (Ours)
the number of blocks in (1, 2), in 16,2448,16,,32,,,,12222
learning rate in {0.05, 0.01, 0.005). weight decay in 5e-4, 5c-5),
5e-4,
DGT (Ours)
the number of blocks in (1, 2}, in [1.2448.16.32244,22222.
We implement our model (DGT and DGT-light) using Pytorch and Gorch-Geometric. For constructing node sequences, employ three criteria such as BFS, sorting based Personalized PageRank score, and sorting based on feature similarity between base node and nodes in a graph. The detailed hyperparameter settings are in Table
Ours.
17

---

Under review as a conference paper at ICLR 2023
G DISCUSSION
Negative societal impacts. Deformable Graph Transformer (DGT) is a graph Transformer for learning node representations on large-scale graphs. We believe that this paper has direct negative societal impacts. However, similar to other neural networks for graph-structured datasets such as Graph Neural Networks (GNNs), DGT can be utilized for malicious applications. Graph neural networks can be applied to predict unknowable information such religions, political views, and personal preferences based on graph information. If this technology applied to identifying the personalities of voters and influencing their behaviors, it might cause interference in the elections. To mitigate these societal problems, illegal data collection and data harvest should be prevented and benchmark datasets should be released without any private information.
Limitations. Deformable Graph Transformer (DGT) performs deformable attention based on di- verse node sequences. The node sequences play the role of coordinates in 2D images. However, different from the works based on deformable attention in computer vision Zhuu et al. (202T); Xia al. (2022), nodes in graphs do not have the exact positions. So, the position of each node needs to be defined with appropriate mechanisms based on the properties of graphs. In this paper, we utilize multiple criteria for generating node sequences to capture various properties of the graphs for node classification. In other tasks such as link prediction and graph classification, other criteria for generating node sequences could lead to more powerful representations on graphs. We leave for our future work.
18


Reviews:
[{"review_id": "l_OY0qD1fOd", "reviewer": "Reviewer_wsk3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Graph transformers have drawn growing attention in representation learning on graph-structured data. However, their success is limited to small graphs due to the quadratic complexity of the dot-product attention module in transformers. This paper proposes the Deformable Graph Transformer (DGT) to address this issue, by using a deformable graph attention (DGA) module with a linear complexity in the number of nodes. The proposed DGA, inspired by recent work in computer vision, only attend to a small set of key sampling nodes around a reference node. The set of key sampling nodes is learned by learning their positions in a sorted list pre-defined by each reference node based on some similarity criteria with respect to the reference node, such as personalized Pagerank score (PPR), BFS, or node feature similarity. The paper also proposes a positional encoding to use with the proposed DGT. The authors validate the proposed method on several node classification tasks.", "summary_of_the_review": "Despite the efforts made by this work to solve a challenging and important for graph transformers, I recommend weak reject because 1) the presentation of method is imprecise and lacking a lot of details; 2) there are important missing baselines and the reported results seem to be far behind SOTA results; 3) the contribution to positional encoding is over-claimed due to incomplete related work; 4) some hyperparameter studies are missing.", "strength_and_weaknesses": "##### Strengths\n1. Development of efficient transformers is a challenging and important task. To my best knowledge, this is the first work on linear transformer specifically developed for graphs.\n2. The proposed method seems to scale well to large datasets with up to 232k nodes.\n##### Weaknesses\n1. (Presentation of the method) The paper does not do a great job of presenting the proposed method and highlighting the technical novelty. Section 3.2 is not very accessible for readers not familiar with previous work on deformable transformers, and is hard to identify the technical contribution from the previous work. It seems that many new concepts introduced here such as sampling offsets or using interpolation to find the representation at fractional location have already been introduced in [1]. I recommend a separate background section including section 3.1 and more preliminaries of deformable transformers to make the paper self-contained.\n2. (Clarity of the method) The main contribution of the work should be to use a NodeSort module to enable offset sampling and thus key node sampling. However, the presentation of this module is very short and there is even no detailed description about each sorting criteria, neither a reference provided. Besides, I am not sure some of them have a proper definition of ordering. For instance, if I understand correctly that BFS denotes the breadth-first search (the paper uses this abbreviation without giving the full name), then its order cannot be unique and could be exponential in the worst case. I expect more a more detailed presentation of all these sorting criteria. In addition to this, I also found some other missing details. For instance, how the offsets are computed is only described in the caption of Figure 1, which largely reduces the readability of the paper.\n3. (Missing baselines) There are a few recent graph transformers leveraging better the structural information about the graph such as [2, 3]. In particular, [3] explore different linear/sparse attention methods from NLP, such as Performer or BigBird, to make graph transformers more scalable. I expect an empirical comparison with these methods to justify the practical impact of DGT.\n4. (Weak results on ogbn-arxiv) A quick check on the leaderboard of [ogbn-arxiv](https://ogb.stanford.edu/docs/leader_nodeprop/#ogbn-arxiv) suggests that the SOTA performance is around 76% while the best performing methods in Table 1 of this work only achieves 71%, which is far behind the real SOTA. I am skeptical about the so-called SOTA performance on other datasets and the claim in the abstract that DGT achieves SOTA performance on 7 datasets.\n5. (Novelty of positional encoding) The proposed Katz positional encoding is very similar to the random walk positional encoding introduced in [4, 5], which have already been widely used in many graph transformers. I recommend the authors to check and correct the claims on this contribution.\n6. (Missing hyperparameter studies) Comparison of using different sorting criteria is shown in Table 3. However, the results are incomplete and results for only using PPR or Feat are not given. In addition, a study on the effect of different values of $\\gamma$ would also be useful as its search space seems to be much larger than other hyperparameters.\n\n##### Minor comments\n1. The way of measuring FLOPs could be variable and ambiguous. Could the authors elaborate more on how they measured the FLOPs for different methods? Could the authors also report the runtime per epoch?\n2. In section 3.3, \"path\" should be replaced with \"walk\" that allows repeated nodes.\n\n##### References\n[1] Zhu, Xizhou, et al. \"Deformable DETR: Deformable Transformers for End-to-End Object Detection.\" ICLR 2020.\n\n[2] Chen, Dexiong, et al. \"Structure-aware transformer for graph representation learning.\" ICML 2022.\n\n[3] Rampášek, Ladislav, et al. \"Recipe for a General, Powerful, Scalable Graph Transformer.\" NeurIPS 2022.\n\n[4] Dwivedi, Vijay Prakash, et al. \"Graph Neural Networks with Learnable Structural and Positional Representations.\" ICLR 2021.\n\n[5] Li, Pan, et al. \"Distance encoding: Design provably more powerful neural networks for graph representation learning.\" NeurIPS 2020.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "lO6cCR50VwB", "reviewer": "Reviewer_PKKU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes deformable graph transformer (DGT) to efficiently perform attention on graphs. The deformable graph transformer mainly consists of two components: deformable graph attention and Katz positional encoding. Experiments on eight datasets show better performance.", "summary_of_the_review": "The deformable graph attention module should be presented in a clear way. The reduction of complexity should be explained further.", "strength_and_weaknesses": "Strengths \n1. The research problem is a fundamental and crucial one.\n2. The experimental results show superior accuracies and efficiency (FLOPs).\n\nWeaknesses\n1. The novelty and technical contribution are limited.\n2. It is unclear for the deformable graph attention module.\n3. It is unclear why the proposed method has lower computational complexity.\n\nDetailed comments:\n1. What is the motivation to choose personalized pagerank score, bfs, and feature similarity as sorting criteria?\n2. For NodeSort, 1) how to choose the base node, or is every node a base node? \n2)“NodeSort differentially sorts nodes depending on the base node.” Does this mean that the base node affects the ordering,  affects the key nodes for attention, and further affects the model performance?\n3)After getting the sorted node sequence, how to sample the key nodes for each node? And how many key nodes are sampled？is the number of key nodes a hyper-parameter? 4)What are the Value nodes used in Transformer in this paper? 5)How to fuse node representations generated by attention for different ranking criteria.\n3. Intuitively, the design of deformable graph attention is complicated, and the Katz positional encoding involves the exponentiation of adjacency matrix, so Is the computational complexity really reduced? Where can the reduction in complexity be explained from the proposed method compared to baselines? or just from the sparse implementation? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hu1R3mLicrg", "reviewer": "Reviewer_KagM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work propose DGT, a transformer architecture for dealing with graphs with a large number of nodes.\nDGT combines an adaptation of the deformable attention scheme to graphs and a new learnable position encoding for nodes.\n\nThe deformable attention mechanisms consists in sorting all the nodes in the graph w.r.t. some criterion viewed from all nodes (e.g., BFS). This is a pre-processing step. Then, for a given query node and each combination of (sorting criterion, head), for each k of the K first nodes, a deformable attention is computed. More precisely, the deformable attention interpolates the values of all the nodes w.r.t. node k in the sorting using the RBF kernel.\n\nOn the other hand, the new Katz position encoding counts all paths between a given node and all the others with decaying weight for longer paths. A subsequent processing by a MLP makes it learnable.\n\nThen, the authors demonstrate the superiority of their approach on several homophilic and heterophilic node-classification datasets in terms of accuracy and FLOPs. Some ablations study are performed to demonstrate the usefulness of their relative multi-criteria search and position encoding separately. Finally, the work study the nodes that are selected by their attention mechanism compared to Graphormer.\n", "summary_of_the_review": "This work combines two effective mechanisms to propose a graph transformer scaling to large number of nodes with very good performance in terms of accuracy and FLOPs. It also has some defaults such as lack of clarity for one of the two mechanisms (sampling offset in DGA), claims about novelty of Katz PE and about how classical architectures aggregate \"irrelevant\" nodes that could be better supported. I also think it would be interesting to demonstrate the usefulness of DGT for graph classification. \n\nOverall, I think the pros outweight the cons and I recommend acceptance. I would further raise my score if these concerns are answered.", "strength_and_weaknesses": "Strengths:\n- This work address an important problem, namely how to make graph transformers work when the number of nodes is large.\n- The strategy proposed by the authors seems very effective on all datasets both in terms of accuracy and FLOPs.\n- The authors provide ablations to study the effectiveness of their two contributions (DGA and Katz PE).\n\nWeakness:\n- Although the paper is mostly well-written, I had a hard time understanding how DGA works. In particular, the idea of sampling offsets could be made more clear both in the text and in the figure (I do not understand what do the arrows do in the blue boxes in the center) so that the work is more self-contained.\n- The claim that other architectures query irrelevant nodes could be backed more rigorously (see below).\n- I am not sure the comparison are fair or at least clear in terms of model size (see below). \n- It would be even more convincing to demonstrate that DGT is also good at graph classification/regression tasks", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PtY_ANExCU", "reviewer": "Reviewer_HE3Q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper propose a new graph sampling mechanism for reducing the computational complexity in full attention of graph transformer. The sampling mechanism takes structural and semantic similarity into consideration. Experimental results show the effectiveness of the proposed method. Additionally proposed positioanl encoding enhances the performance of the model. ", "summary_of_the_review": "See Weaknesses. I'm willing to raise my score if my concerns are well addressed.", "strength_and_weaknesses": "Pros:\nThe motivation makes sense. The paper is easy to follow. \n\nCons:\n1. The proposed method seems to be a graph sampling mechism + full attention on the sampled node subset. Therefore the claim of \"sparse attention\" should be clarified.\n2. It's strange to run a Transformer-based graph model on full graph for node representation tasks without any graph sampling methods (e.g., random walk). Therefore, the comparision seems unfair to me from both the performance and the computation cost perspectives. More detailed benchmarking experiments with graph sampling methods will make the paper more solid.\n3. The proposed Katz PE seems to be an important component contributing to the final performance, but the motivation of the Katz PE is less relevant to the main motivation of this paper. Therefore, it makes the solidness of the main contribution of this work (the graph samping mechnism) weak.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "PkVBrHdLdf", "reviewer": "Reviewer_Xtmm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a new transformer-like architecture for processing graphs. The main component is a special sparse attention module that considers only the neighbor nodes based on certain metrics. These metrics can be either structure or feature-based. For sampling from the neighborhood, it uses learned offsets. The authors also propose a novel position encoding method for the nodes in the graph.\n", "summary_of_the_review": "\nTo recommend acceptance, I would like to see the following:\n- Clarity has to be improved\n- Specification of the preprocessing step in a clear way, including in the complexity calculation\n- I would like to see an analysis of what the KatzPE does\n- Some analysis on why the DGA's performance is very close to random\n\n\nQuestions to clarify:\n- How do the sorting criteria work? What are they exactly? What is their input? Do they have learnable parameters?\n- The paper claims that it is more efficient than the transformer-based methods. However, it does not consider the preprocessing step, which can be very slow (although it has to be done only once). Also,  \"feature similarity\", as far as the name suggests, is just ordinary attention, so it should be the same speed.\n- \"Although restricting the attention scope to local neighbors is a simple remedy to reduce the computational complexity, it leads to a failure in capturing local-range dependency, which is crucial for large-scale or heterophilic graphs.\" -> do you have any reference for this? According to Table 3, even using random nodes is almost as good as the best model. Isn't BFS doing just that?\n- You mention that \"DGT-light\" uses a single sorting criterion. Which one?\n- All of Eq. (4) is position based, but the positions are defined by the most relevant features (by S). The attention matrix only depends on the query node's feature and not the key's (it is just a fixed function for a given key index, k). This can act as a regularizer because the network can hardly choose individual, well-defined nodes to attend to. This can by itself improve performance.\n- What is p? It can be inferred that it's probably an offset vector, but it would be nice if that is written in the paper.\n- It would be nice to visualize p for some learned tasks. It would be informative about how far the model attends.\n- What value of \\gamma is used in eq (5)?\n- \"A major issue with positional encoding on graphs is the absence of absolute positions of nodes, unlike other domains.\" - what does it mean to have absolute positional encodings in a graph? What defines the ordering of the nodes?\n- I don't see why KatzPE makes sense. It would be nice if the authors could add some more explanation. For me, it seems more like some kind of structure descriptor added to the nodes than it has anything to do with positions.\n- A_k in Eq. (6) is of a fixed size. Does this mean that, unlike the transformer-based methods, KatzPE depends on the graph size? (for big graphs, this limitation is not present since there are only N' anchor nodes)\n- It would be worth writing down that the so-called sampling is not actually an active sampling operation but just taking the features from the learned offsets. It can be confusing on the first read.\n- Could you provide more details on how O(NC^2T + NKC^2T + WNKCT) becomes O(NC^2T + WNKCT) in Appendix A? Why does swapping the interpolation help with this?\n- In 4.4, Figure 2, a should be Figure 2a\n- In Appendix C.2, the list of parameters should be a table\n", "strength_and_weaknesses": "Strengths:\n - better performance on various datasets\n - the topology-based sorting ideas are interesting and novel to the best of my knowledge\n\n Weaknesses:\n  - some parts (for example, the preprocessing) are not specified in the paper\n  - the paper is difficult to read\n  - some design choices need more justification\n  - very complex\n  - claiming that this method is the best among the transformer-based ones is somewhat unfair. The main difference between the transformer-based methods and the GAT-style GNNs is the unrestricted attention, but here the preprocessing step introduces very similar restrictions. \n\nThe main weakness of the method:\n- From Table 3, picking nodes at random is not much worse than choosing the nodes in the smart way proposed by the paper. This is surprising and questions what deformable attention does and its importance.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject