Reach the Remote Neighbors: Dual-Encoding Transformer for Graphs
Authors: Lingbing Guo
Zequn Sun
Qiang Zhang
Huajun Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: konwledge graph prediction
node classification
graph property prediction
MSA Transformer

Abstract: Despite recent successes in natural language processing and computer vision, Transformer suffers from the scalability problem when dealing with graphs. Computing node-to-node attentions is infeasible on complicated graphs, e.g., knowledge graphs. One solution is to consider only the near neighbors, which, however, will lose the key merit of Transformer that attends to the elements at any distance. In this paper, we propose a new Transformer architecture, named dual-encoding Transformer (DET), which has a structural encoder to aggregate information from near neighbors and a semantic encoder to focus on useful semantically close neighbors. The two encoders can be incorporated to boost each other's performance. Our experiments demonstrate that DET achieves superior performance compared to the respective state-of-the-art attention-based methods in dealing with molecules, networks and knowledge graphs.

Under review as a conference paper at ICLR 2023
REACH THE REMOTE NEIGHBORS: DUAL-ENCODING TRANSFORMER FOR GRAPHS
Anonymous authors Paper under double-bling review
ABSTRACT
Despite recent successes in natural language processing and computer vision, Transformer suffers from the scalability problem when dealing with graphs. Com- puting node-to-node attentions is infeasible complicated graphs, e.g., knowledge graphs. One solution is to consider only the near neighbors, which, however, will lose the key merit of Transformer that attends to the elements at any distance. In this paper, we propose a new Transformer architecture, named dual-encoding Transformer (DET), which has structural encoder aggregate information from near neighbors and semantic encoder to focus on useful semantically close neigh- bors. The two encoders can be incorporated to boost each other's performance. Our experiments demonstrate that DET achieves superior performance compared to the respective sfate-of-the-arr attention- based methods in dealing with molecules, networks and knowledge graphs.
INTRODUCTION
Transformer has become one of the most prevalent neural models for natural language processing
(NLP) (Vaswani al. 2017 7 Devlin et al. 2019). The self-attention mechanism leveraged by
Transformer has already been extended to graph neural networks (GNNs), e.g., GAT (Velickovic
al.
2018) and its variants (Wu al. 2019 Vashishth et al., 2020 Chen al. 20216] Kim & Oh
2021 Nevertheless, these models only consider the near (usually one-hop) neighbors, which may
violate the original intention of Transformer that attends to the elements at distant positions.
Recently, Graphormer (Ying et al. 2021) starts to leverage the standard Transformer architecture for graph representation learning and has achieved superior performance on many benchmarks. However, in its scenarios of graph property prediction, the datasets are small graphs (e.g., small molecules). The full node-to-node attention leveraged by Graphormer makes it inapplicable to large graphs with millions of nodes, such as knowledge graphs (KGs) social networks. The same problem also appears in the computer vision (CV) area, yet has recently been tackled by patching pixels to patches and then to windows in hierarchical fashion (Dosovitskiy al., 2021 Liu al. 2021b). These works inspire us to explore the possibility of using one universal Transformer architecture as the general backbone to model graphs of different sizes.
In addition to many self-attention-baree al. 2018; Wu al. 2019; Ye et al. 2019 Chen al., 2021b Kim & Oh 202T), some existing works introduce multi-ho hopp (usually 2- or 3 3-hop) neighbors (Abu-El-Haija et al, 2019 Sun et al. 2020). However, they still concentrate on the local information and fail obtain useful information from the remote nodes. Capturing the remote correlations is one of the most important characteristics of Transformer, because the rich context not only boosts the performance for local information. For example, attending to the distant nodes may be helpful even highly homophilic graph, considering the existence enormous missing links (Ciotti et al. 2016).
methods considering only one-hop neighbors (Schlichtkrull
also avoids over- wer-fitting
In this paper, we propose dual-encoding Transformer (DET). In DET, we consider two types of neighbors, i.e., structural neighbors and semantic neighbors. Structural neighbors are the near neighbors leveraged by most existing GNNs (Vashishth et al. 2020 Chen et al. 2021b] Kim & Ohl (hen
202I). By contrast, Semantic neighbors, i.c., the remote neighbors, are the semantically close nodes but may be remote from the node of interest in structure.

---

Under review as a conference paper at ICLR 2023
structural neighber
node interest
feed to the structural encoder
strictural emhesidings
0 semsniic neighbou
oxrput
food the semanii enooder
semamlic embeldlins
node
node embeddings
Figure Overview of DET. Structural neighbors are local neighbors connected with the node of interest on the graph, while semantic neighbors are remote nodes with similar semantics to the node of interest. The two encoders focus on encoding different aspects of neighboring information, and thus are capable of complementing each other.
Figure [ shows the basic idea of DET. For structural encoding, we use the standard self attentioo layer to encode the structural neighbors. For semantic encoding, we use a modified linear attention layer to encode the semantic neighbors. The dual encoding ensures both local aggregation and global connection, and also enables them to benefit from each other through back propagation.
The idea of reaching remote neighbors is inspired by MSA Transformer (Rao al. 2021) and AlphaFold 2 (Jumper et a (02I)) They query the genetic database to fetch the similar sequences (i.e., proteins) as "family members". The difference that the family members in DET (i.e., semantic neighbors) are obtained by self supervisd learning rather than asking for external resources. Briefly, we convert this problem to a learning task to find the distant nodes that are as important as local neighbors. We then view local neighbors positive examples and randomly sampled distant nodes as negative examples, constructing a standard contrastive learning. Furthermore, we propose to use the semantic operator to estimate the score between the node of interest and others. It is learnable function to compel the encoder to value the semantically close nodes.
The proposed DET is capable of achieving superior performance on various graph learning tasks. (1) For graph property prediction, DET outperforms the best-performing methods on the PCQM4M- LSCvl NNakata Shimazaki (017)) and ZINC (Dwivedi al., (020) datasets; (2) For node classifi- cation, DET obtains competitive or better performance compared with the state-of-the-art attention- based methods, on several prevalent benchmarks (e.g., Cora, PPI, and ogbn-arxiv) (Yang al.. & Shimazaki] [017]] Zitmik & (akkovec|[011]] (3) For KG completion (a.k.a., entity prediction), DET achieves the state-of-the-arr performance on both FB 15K-237 (Toutanova & Chen 2015) and WN18RR (Dettmers et al. 2018).
2 RELATED WORKS
We split the related literature into three parts: non-local GNNs, self-attention, and position embedding.
Non-local GNNs
Some methods also investigate how capture the relationships among discon-
nected nodes (Pei et al. 2020
Yao et al.] [0200] Liu et al. 202 Min et al. (022). Specifically, Geom-GCh (Pei et al.] 2020 learns the aggregation purely based on embedding distance, while
Non-local-GNNs (Liu et al.] 202 uses the attention scores from virtual node to other nodes as a sorting metric to find non-local neighbors. However, they only focus on modeling networks and are evaluated on multi-classification tasks with few classes. They also do not distinguish between
remote nodes and direct neighbors. (Yao et al. 2020 Min et al. [2022) leverage hand-crafted features
to find the useful remote nodes, which are less relevant to work.
Self-attention--basee neural models, such as Transformer, have recently become the de facto choice in NLP, ranging from language modeling and machine translation (Devlin al. 2019 Vaswani et al. (017) to question answering (Yang et al., 2019 Yavuz et al.) 2022) and sentiment analysis (Cheng al.) [222]] Xu et al. 2019a). Transformer has significant advantages over conventional sequential models like recurrent neural networks (RNNs) (Williams & Zipser 1989
Self-attention
Hochreiter & Schmidhuber 1997) in both scalability and efficiency.
2

---

Under review as a conference paper at ICLR 2023
Position Embedding Position embedding is one of the most important modules of Transformer. Transformer variants in different fields typically customize different designs in this module. For example, ViT and its followers (Dosovitskiy et al. 2021 Fan et et. 2021 Han et al. (222)) sequentially index the patches and encode the indices as ID position embeddings. Swnnfraanr (Liu et al.
e proposes the 2D-aware relative position biases, which employs a learnable matrix record pairwise patch position information in the window.
In addition the position information, other prior knowledge can also be injected attention biases or position embeddings into Transformer, which becomes the key to applying Transforme
on graphs (Ahn et al., [021]] Chen et al., 2021a Dwivedi & Bresson, 202T] Kreuzer al., 2021
Ying et al. 2021). For example, GT (Dwivedi & Bresson (221]) replaces the sinusoidal positional
embeddings by the Laplacian eigenvectors. Graphformer (Ying al. 2021) encodes centrality and
shortest path distance into embeddings, and then incorporates them position embeddings into Transformer. HiuER (Chen et al., (02Tb) adds the edge type (i.e., relation) information of KGs when
encoding entity embeddings.
METHODOLOGY
In this section, we present the details of DET. We start from the preliminaries and then introduce the dual-encoding process. Finally, we illustrate how to train DET model.
3.1 PRELIMINARIES
We first introduce the terminologies and notations that will be used in the following sections.
Graph We define a graph as G = (V, E), where V = fur U2 Up } is the node set, and = fer, Cm, is the edge set. and denote the number of nodes and edges, respectively. In practice, different tasks often have more complicated graph structures. For example, molecular graphs and KGs have edge types (i.e., chemical bonds and relations). We do not discuss the details and follow the general setting to process these specific features (Chen et al. 2021b Ying et al. 2021).
GNN and Self-attention Without loss of generality, we define a GNN as a neural network that learns group of weights aggregate the embeddings of the one-hop or multi-hop neighbors for the node of interest. In this sense, self-attention can be naturally treated as a GNN model. Let Q E Rexh K R V E Raxh denote the query, key, and value matrices, respectively. In this paper, they are the same node embedding matrix. / denotes the hidden layer size. Self-attention calculates the attention scores follows:
QK
A = Softmax(
)
(1)
Vh.
where A R records the node-to-node attention scores. We then aggregate the node embeddings with the following equation:
= AV,
(2)
where H E Raxh is the output embedding matrix, with each row denoting the embedding of node.
Linear Attention
The computational complexity of the above dot-product implementation is (2n))) (without considering the hidden layer size). As the number of nodes increases, the cost becomes unacceptable. GAT (Velickovic et al.) 2018) proposes a lincar self-attention implementation to mitigate this problem by only considering the one-hop neighbors:
Bi = ob (Wv; Wv;)),
where Bi denotes the attention from the node of interest i; to neighbor by. Vi, V. R² are the embeddings of e; and Uj. respectively. b E R and W E Raxh are weight vector and matrix, respectively. a is the activation function and denotes the concatenation operation. The linear attention does not consider the correlations within neighbors, and thus its computational complexity cut down from (2n²) to a(m). Note that, it is not necessary to use one-hop neighbors as keys in linear attention. Some existing works also consider multi-hop neighbors (Sun et al. 2020
3

---

Under review as a conference paper at ICLR 2023
Table The occurrence frequency of entities in FB 1B15K-237 and WN18RR, in term of hops.
Algorithm 1 Dual-encoding Transformer
1: Input: graph 9 (V, E), the main predic- tion loss Emain the structural encoder Mat. and semantic encoder Mas
Dataset
1-hop
2-hop
3-hop
5-hop
WN18RR
2.7
8.9
30.5
483.8
FB15K-237
20.3
1781.4
64,774.9
2: Initialize all parameters;
3: repeat
4: Update the semantic neighbors;
neighbors
for each batch data (X X Xsex Y do
Query
trabel
6:
Ha + -Mar((e (Xt) (Equation (4
H.e + +Mage (Xxe) (Equation
8:
H +- Ha + Hsci
Results
Compute funn (Equation 77):
10: L Lmmin (H, H) ben
11: Update the parameters according to L:
Figure 2: A comparison between MSA and mantic neighbors. The left figure is sliced from Jumper et al. (202T). The right figure is an exam- ple from WordNet (Miller 1995).
12:
end for
13:
until the performance on the validation set
converges;
3.2 STRUCTURAL ENCODING
The standard dot-produee attention can be easily extended on the small graphs. We add a virtual node v. (Devlin al. 2019) the context node connected with all nodes in G. Then, the output representation for Ve can be regarded as an embedding of G. For the large graphs like KGs or networks, perform self-attention on the local subgraph 93 given the node of interest v, Therefore, the output embedding for node 0; is
h ,,(C,JUN(())
Σ
A
where hy" denotes the output of the structural encoder for Us Acj denotes the attention score from the context node to the neighbor uy. .N(x;) denotes the set of local neighbors Jone-hop neighbors in our implementation) for U;- Follow the existing works (Chen et al., 2021b Ying et al. 2021), we accordingly add the centrality, relation type, shortest distance path information special position embeddings to the encoder. The details can be found in Appendix
3.3 SEMANTIC ENCODING
The structural features sometimes are unreliable for identifying a neighbor. For example, if the node of interest has a large amount of neighbors, many of them inevitably have similar or identical structural features (c.g., shortest path distance to v.). This problem is even more serious when they all one- or two-hop neighbors. However, if we directly aggregate more-hop nodes, the sheer quantity of available information will overwhelm the neural network.
Table summarizes the average frequency of entities appearing others' neighbors in different hops. We can find that the two- or more-hop neighbors of a node are shared by many others, which is why current GNNs rarely consider multi-hop hop neighbors. This phenomenon also reveals the over-smoothing problem to some extent. To make the node of interest more distinguishable to the classifier, weighting its one-hop neighbors is usually reasonable due to the less redundancy. Therefore, make the following hypothesis:
Hypothesis The one-hop neighbors are the most informative features to identify and represent the node of interest.
Recent successes (Rao et al., 2021 Jumper et al. 202I) biological science demonstrate that using the information provided by the family members can help protein structure prediction. Specifically, they leverage multiple sequence alignment (MSA) (the results of biological sequence alignment) to make use of the information within an evolutionary family. The protein sequences in family are assumed to have a common ancestor or an evolutionary relationship. Therefore, they may also share some important sub-structures in protein folding.
4

---

Under review as a conference paper at ICLR 2023
If we view the embedding of node a kind of sequence, then the remote neighbors used in semantic encoding should have similar embeddings to the node of interest. We illustrate this idea in Figure 2 our basic idea is to view node embeddings as protein amino acid sequences with fixed length. Then, we can make use of the insight from the well-known MSA Transformer and AlphaFold 2. To this end, need to find the family members (that share similar evolutional characteristics and relationships) of our "protein". In their original implementation, this step is done by querying an external gene database. our case, we propose the semantic encoder find such family members. Therefore, we make the second hypothesis:
The distant nodes that have a high embedding similarity with the node of interest are important features for this node.
Hypothesis
In this paper, we estimate the similarity score by learnable neural function Ss RR R - R:
fv(v., = v.
-1-o( (vv (v. bb),
(5)
where @ is the semantic difference operator. In fact, the choice of è is flexible as long as it can reflect the similarity between V, and Vj. We use the weighted difference as O) which can easily extended to matrix operation. W, E R and bg E E are the weight and bias, respectively. We use Sigmoid as activation to normalize the difference to (0, 1) and then convert it to similarity score. Therefore, the output embedding for semantic encoding is written as follows:
h
Σ
B
BEEA
Σ
L.(:.Vy)Vy
(6)
()))
where B E Rax" records the node-to- no-dee semantic attention scores estimated by f. in Equation 5 (x;) is the semantic neighbor set. In our implementation, it is sampled from the top candidates (top 10% in setting) during training.
We then define the semantic neighbor fetching loss to learn ss:
(un( =
1
Σ In (f.((v..)))) + (W-()i) BLEN-(())
Σ
In vfs(s..
(7)
WV(wi) eyE)((.)
where (1;) is the positive example set that includes the local neighbors (Hypothesis] of Uú and N- is the negative example set in which the negative examples are randomly-sampled distant nodes (Hypothesis{2 2 us. Therefore, the learning process Ss is self-supervised and can be jointly optimized with the main task loss.
3.4 DUAL-ENCODING TRANSFORMER
Algorithm We illustrate the implementation of DET in Algorithm and summarize the overall training process as follows: We first initialize the input embeddings and all parameters of DET. For each epoch (or every few epochs), we first draw semantic neighbors from the top 10% candidates (according to Equation (5) for each node. In each batch, we feed the structural encoder with the structural neighbors of the input nodes, and the semantic encoder with the semantic neighbors. We combine the output embeddings of two encoders by weighted addition and jointly minimize the main task loss and semantic neighbor fetching loss.
Computational Cost We find the total training time does not increase too much compared with the baselines. The design the semantic operator e in the semantic encoder is simpler than the linear attention, which only increases small number of parameters. Although fetching the semantic neighbors needs to iterate all nodes (yields a time complexity of n²), we do not compute them on the fly. Instead, we update semantic neighbors of each node every few epochs, improving both efficiency and robustness. Hence, the overall training time remains at the same level (see Appendix B for the detailed statistics).
5

---

Under review as a conference paper at ICLR 2023
Table 2: Graph property prediction results on the PCOM4M-LSCvI dataset.
Table 3: Graph property prediction re- sults on the ZINC dataset.
Model
#param.
validate MAE
Model
#puram.
test MAE
GCN
2.0M
0.1318
0.1691
GCN
505.079
0.367
DeeperGCN
25.5M
0. 1019
0.1398
GraphSage
505,34]
0.398
GraphSage
509,549
GIN
3.8M
0.1203
0.1537
GaedOCN-LSPE
0.090
GAT
$31,345
0.384
GT
83.2M
0.0955
0. 0.1408
GT
588,929
0.226
Graphormer
47.1M
0.0582
0.1234
Graphormer
489,521
0.122
DET
47.1M
0.0546
0.1212
4
EXPERIMENT
We conducted experiments variety of benchmarks to verify the effectiveness of DET. We uploaded the source code and reported the dataset statistics and parameter settings in Appendix
4.1 GRAPH PROPERTY PREDICTION
Datasets We evaluated DET on the graph property prediction benchmarks PCQM4M-LSCv1 HHu al., (021) and ZINC (Dwivedi et al. 2020). The former is used in the recent Open Graph Benchmark Large-Scale Challenge, while the latter is popular dataset used to evaluate molecular graph representation learning methods. Considering that the number of nodes in each graph is very small (usually less than 50), directly perform attention operations the whole graph. Therefore, we removed the semantic neighbor fetching loss this experiment.
Baselines We compared DET with the state-of-th of--hh--ttt-tttto methods: the attention- based GAT (Velick ovic et al. 2018), GT (Dwivedi & Bresson 2021) and Graphormer (Ying al. 2021): and other recently developed GCN (Kipf & Welling 2017), GraphSage (Hamilton et |l.] 2017) GIN (Xu et al.)
2019h), DeeperGCN (Gilmer 2017) and CatedGCN--LSP. (Dwivedi al. 2022).
Results Table 2 and Table summarize the experimental results measured by mean average error (MAE) on the two datasets. Due to the inaccessibility of the testing data on PCQM4M-LSCvI, we alternatively report the MAE results on the training and validation sets.
Overall, DET outperformed all the baseline methods on PCQM4M-LSCVI. Compared with
Graphormer that only considers encoding structural information with Transformer, DET signifi- cantly improved the performance, with 6.2% and 7.4% MAE decline on PCQM4M-LSCv1 and ZINC, respectively. Furthermore, the number model parameters still maintained the same level to that of baselines. We also observed that DET had more significant advantages over other Transformer-basee methods on ZINC, Although GatedGCN- had a better result, we argue that is feasible to use it structural encoder to obtain better performance.
4.2 NODE CLASSIFICATION
Datasets We evaluated DET on five benchmarks that are generally used for node representation learning. Specifically, Cora, CiteSeer, and PubMed (Yang et al. 2016) are three citation network datasets
used commonly used in the transductive setting, while PPI (Zitnik Leskovec 2017) is well- interaction dataset in the inductive setting. ogbn-arxiv (Nakata & Shimazaki 2017) is large citation network dataset. Most experiment settings follow (Kim & Oh] 2021)) and we repeated experiments 100 times Cora, CiteSeer, and PubMed with random seeds, and 30 times on PPI and oggbn-axiv, to produce reliable results and ensure a fair comparison.
Baselines We selected the attention iitention-bbse base methods GAT (Velickovic et al. 2018), CGAT (Wang et al. 2019a), Graph-Ben Berph-Bert (Zhang et al.) (2020) and SuperGAT (Kim & Oh 202 1b as baseline methods, In addition, other GNN-based methods like GCN (Kipf & Welling 2017). GraphSage (Hamilton et al. 2017) and GCN+NS (Zheng et al., 2020) were also added for comparison.

---

Under review as a conference paper at ICLR 2023
Table Node classification results on five benchmarks (accuracy for Cora, CiteSeer, PubMed, and ogbn-arxiv; F1-scor for PPT). The results of Graph-Bett Bert are from Zhang et al. 2020
Model
Cora
CiteSeer
PubMed
PPI
ogbn-arxiv
GCN
81.5
70.3
79.0
61.540.4
33.31:.2 $4.6:10.3
GraphSage GCN+NS
82.1=10.6
71.911.9
78.0=0.7
59.0
1.
7..1
GAT
83.0
72.51:0.7
79.0-0.4
72.2:20.6
54.1
CGAT
81.41:11
70.11:0.9
18.1=100
68.3-41.7
Graph-Bert
1.
71.2400.8
1.3
SuperGATTp
82.7:00.6
72.5+:0.8
81.3=005
74.4400.4
54.5=0.3
DET
84.6
72.810.5
81.8
74.1
55.7.10.3
Table 5: KG completion (entity prediction) results on FB FB15K-237 and WNISRR.
FB FBIK--237
WN18RR
Model
MRR
MR
Hits @1
Hits @ 10
MRR
MR
Hits@1 1
Hits@ 10
TransE
.310
199
.218
.495
.232
5,249
.061
.522
RotatE
.338
177
.241
.533
.476
3,340
.428
.571
TuckER
.358
.266
.544
.470
.433
.526
CoKE
.364
.272
.549
.484
.450
.553
CompGCN
.355
197
.264
.535
.479
3,533
.443
.546
HiLER
.373
158
.279
.558
.503
2,268
.62
.584
DET
.376
150
.281
.560
.507
2,255
.465
.585
The results are shown in Table from which we can observe that DET outperformed the attention-based methods on most datasets except PPI. Although SuperGAT'sD had better performance on this dataset, we argue that it is no contradiction to incorporate SuperGAT'su as structural encoder into DET obtain a stronger model.
Results
Interestingly, the attention-based methods unanimously performed worse than the GCN-based method GCN+NS on CiteSeer. SuperGATss and CGAT even had the same or worse results compared with the original GAT. Nevertheless, we observed an improvement from GAT to DET. This result empirically demonstrates the strength leveraging semantic neighbors.
4.3 KG COMPLETION
We conducted experiments the KG completion (a.k.a., entity prediction) task. The main target is to predict the subject entity (or object entity) given an incomplete triple. We evaluated DET two benchmark datasets FB F5552237 (Toutanova & Chen 2015) and WNI8RR (Dettmers) et al. 2018), which are sampled from the real-world KGs Freebase (Bollacker et al. 2008 and Word et (Miller 1995), respectively.
Datasets
Baselines We chose the best- sestt-eefrminng entity prediction methods as our baselines: the TransE- family methods TransF (Bordes al. 2013), RotatE (Sun al., 2019), and TuckER (Balazevic et al. 2019), and the attention-hased methods CoKE (Wang et al. 2019b), CompGCN (Vashishth et al. 2020), and HitER (Chen al. (0211). Specifically, CoKE and HitER also leverage Transformer encode the structural information.
Results We report the main results on Table It is clear that DET surpassed all the baselines across all datasets and metrics. The improvement on MR (mean rank) most significant, which implies that DET learned better embeddings for all entities, not only for the top ones favored by Hits 1.
Overall, DET achieved competitive performance on all three types tasks, which demonstrates its effectiveness and generality in modeling graphs.
7

---

Under review as a conference paper at ICLR 2023
Table 6: Ablation study results on different datasets (1: higher better; 1: lower is better. X: unavailable entry). St. and Se. are the abbreviations of Structural and Semantic.
encuder
Fetching
PubMed Accuracy
FB15K-237 Mean Rank.
WNISRR Mean Rank.
MAEL
Accuracy
Accuracy
X
84.6
72.8
81.8
150
2.255
0.113
82.6
72.7
78.1
151
2,305
0.122
84,0
71.6
80.9
158
2.268
84.1
72.5
81.5
X
X
0.515
83.1
72.6
77.7
$4.5
Accuracy
14.4
41.5
41.
14.0
0.40
40.5
0.47
13.6
0.55
400
(8)
Cora
(b) CoraFull
(c) Chamelcon
Figure Accuracy on three datasets with different homophily (Cora Yang 2016); 0.83,
CoraFull (Bojchevski & Günnemann 2018): 0.59, Chameleon (Rozemeerczki et al. 2019): 0.21),
w.r.t hyper-paramend (average of" runs). The homophily statisties are from (Zhu et al. 2020
5
FURTHER ANALYSIS
To better understand DET, we design three experiments to explore and evaluate DET in depth.
5.1 Is EVERY MODULE IN DET USEFUL?
We conducted ablation studies verify the effectiveness of each module in DET. We used six datasets in different tasks and present the results in T We removed the modules from DET step-by-step while keeping identical syper-parameter settings throughout the experiments.
Semantic Neighbor Fetching The semantic neighbor fetching loss is undoubtedly important DET. No matter if combining two encoders or only using the semantic encoder, integrating with the semantic fetching module had better performance in most cases. The improvement was most notable on PubMed, where it yielded 3.7% and 3.8% of accuracy increases, respectively. The mean rank results on WNISRR also got worse without the fetching loss.
Semantic Encoder If do not consider the semantic neighbor fetching loss, the semantic encoder itself still useful to DET? Unfortunately, we find the answer ambiguous. For Cora, PubMed, and WNISRR, when we did not employ the fetching loss, DET with the semantic encoder performed much worse than DET without the semantic encoder. But we observe that the situation was reversed on CiteSeer and 1B155-237, In fact, when we only consider one-hop neighbors, the semantic encoder without fetching loss is just "minus" attention layer. It may have its pros and cons compared with the standard doo-puo attention layer on different datasets. this sense, the semantic fetching loss is who endows the semantic encoder with the characteristic.
the ZINC dataset, where the model can apply attention operations on the whole graph, the semantic encoder was capable of estimating the semantic similarity of remote neighbors to the node of interest without the help of the fetching loss. Therefore, we can see that the dual-encoding version of DET greatly outperformed the structural encoder only version. Overall, the effectiveness of the semantic encoder is conditioned: must get in touch with the remote nodes.
Structural Encoder The structural encoder also has merits. From the results of the 3-rd and 5-th rows in Table 6 we find that it had better performance than the semantic encoder on all datasets except CiteSeer. We also noticed that only using the semantic encoder had the worst MAE on the ZINC dataset, due to the absence of all structural information.
8

---

Under review as a conference paper at ICLR 2023
From Software
Elovesient (0.47)
furn (0.56)
Video gane indistry (0.97)
(I
interest
clanne
walk: (8 65)
szuuctuaa neighbour
Engfish Langage (8 S33
Nialendo
Afisa (0 81)
Iravdl
semantic neighhons
Shigsu Miyanitoo
aECorppart (0:37)
USA (0
Manel
unsonndized semumiic score
Sony Cooputer En
BONe (0.64)
(a) FB15K-237
(b) WNI8RR
Figure 4: Examples of the semantic attention scores to different types of neighbors.
5.2 THE CORRELATION BETWEEN SEMANTIC ENCODING AND GRAPH HOMOPHILY
In the Introduction section, we mention that the semantic encoding is helpful even on graphs with high homophily. Therefore, we conducted experiment to verify the correlations between the effectiveness of the semantic encoder and the homophily of datasets.
We set a hyper-parameter T to control the combination of the structural encoder and the semantic encoder, which can be written in the following equation:
h 7h + (1-r)h",
(8)
where h, h h denote the combined output, structural output, and semantic output, respectively. By assigning different т, we can control the importance of each encoder in the combination.
The experimental results shown in Figure 3 from which different r existed in all three datasets, but the trends and peaks were different. On highly homophilic 0 to 0.15, and peaked around 7 0.2, then dropped until - = 95. On CoraFull and Chameleon with median and low homophily, we observe that the performance peaked around [0, 0.05] and maintained steady in the interval [0.05, 0.2].
that the performance gap for
dataset Cora, the accuracy first increased from
When 2 0.5, the performance rapidly dropped to minima. Therefore, we may make the following conclusions: (1) the semantic encoder has better effects when the datasets have low homophily. The larger proportion the semantic encoding occupied, the better performance the model achieved; (2) even on the highly homophilic dataset, engaging the semantic encoder with a proper has significant advantages over using only structural encoder; (3) in any cases, properly combining the output of two encoders (i.c., DET) is the best choice.
5.3 How DOES THE SEMANTIC ENCODER HELP THE STRUCTURAL ENCODER?
is worth exploring how the semantic encoder affects the structural encoder. In Figure we illustrate two examples on FB 15K-5K2 237 and WN18RR, respectively. We find that the semantic scores for the structural neighbors are also line with human intuition. In the left figure, the entity USA has low score although it is directly connected to Nintendo by relation service llocation.. The verb precede and accompany obtain relatively low scores in the right figure. These neighbors are not very related to the entities of interest from the human perspective. By contrast, some one-hop neighbors get high semantic scores, e.g.. the well-known director Shigeru Miyamo of Nintendo in FB 157-237 and the verb walk in WN18. They are the more informative entities. For the semantic neighbors, that the exploited remote neighbors are closely related to the entity of interest, as well as the structural neighbors with high semantic scores. For example, Atlay is an important game developer Aggregating such information may be helpful when the model is asked to predict the games related to Nintendo. For the verb travel in WN18RR, move also shares many key features with it.
Nintendo.
CONCLUSION AND FUTURE WORK
In this paper, we propose a new Transformer architecture DET to deal with graphs of different types and sizes. In DET, the structural encoder aggregates information from local nodes while the semantic encoder seeks the remote nodes with useful semantics. The experimental results demonstrate the strong performance of DET three prevalent GNN tasks across 9 benchmarks. We hope DET can bring more insights and inspirations in developing unified Transformer architectures. In future, we plan to adapt DET to the NLP and CV areas.

---

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, volume 97 of Proceedings of Machine Learning Research, pp. 21-29, 2019.
Sungsoo Ahn, Binghong Chen, Tianzhe Wang, and Le Song. Spanning tree-based graph generation for molecules. ICLR, 2021.
Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Tucker: Tensor factorization for knowledge graph completion. EMNLP-IJCNLP, pp. 5184-5193, 2019.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In ICLR, 2018.
Kurt D. Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: A collaboratively created graph database for structuring human knowledge. In SIGMOD, pp. 1247- 1250, 2008.
Antoine Bordes, Nicolas Usunier, Alberto Garcia- Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pp. 2787-2795, 2013.
Jianwen Chen, Shuangjia Zheng, Ying Song, Jiahua Rao, and Yuedong Yang. Learning attributed graph representations with communicative message passing transformer. IJCAI, 2021a.
Sanxing Chen, Xiaodong Liu, Jianfeng Gao, Jian Jiao, Ruofei Zhang, and Yangfeng Ji. Hitter: Hierarchical transformers for knowledge graph embeddings. EMNLP, pp. 10395-10407, 2021b.
Junyan Cheng, lordanis Fostiropoulos, Barry Boehm, and Mohammad Soleymani. Multimodal phased transformer for sentiment analysis. In EMNLP. pp. 2447-2458, 2021.
Valerio Ciotti, Moreno Bonaventura, Vincenzo Nicosia, Pietro Panzarasa, and Vito Latora. Homophily and missing links in citation networks. EPJ Data Science, 5:1-14, 2016
Mark Craven, Dan DiPasquo, Dayne Freitag, Andrew McCallum, Tom Mitchell, Kamal Nigam, and Scán Slattery. Learning to extract symbolic knowledge from the world wide web. In AAAI, pp. 509-516, 1998.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2D knowledge graph embeddings. AAAI, pp. 1811-1818, 2018.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. NAACL-HLT, pp. 4171-4186, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x 16 words: Transformers for image recognition at scale. In ICLR, 2021. /ttpiitttps.//pppeeiieeee wtt::/oormmmdid
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020. URL https:
7/arxiv. org/ hbtp://bb//0000 2003. 00982
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. URL
https://openrevieer net foorumiddwwwinneee jIVSpphh
Haoqi Fan, Bo Xiong, Karttikeya Mangalam, Yanghao Li. Zhicheng Yan, Jitendra Malik, and Christoph Feichtenhofer. Multiscale vision transformers. In ICCV, pp. 6824-6835, 2021.
10

---

Under review as a conference paper at ICLR 2023
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In JCML, pp. 1263-1272, 2017.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pp. 1024-1034, 2017.
Kai Han, An Xiao, Enhua Wu, Jianyuan Guo, Chunjing Xu, and Yunhe Wang. Transformer in transformer. NeurIPS, 34, 2021.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9: 1735-1780, 1997.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: large-scale challenge for machine learning graphs. arXiv preprint arXiv:2103.09430, 2021.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, Alex Bridgland, Clemens Meyer. Simon A A Kohl, Andrew Ballard, Andrew Cowie, Bernardino Romera-Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Ziclinski, Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Sebastian Bodenstein, David Silver, Oriol Vinyals, Andrew W Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis. Highly accurate protein structure prediction with AlphaFold. Nature, 596 (7873):583-589, 2021.
Dongkwan Kim and Alice H. Oh. How find your friendly neighborhood: Graph attention design with self-supervssoon In ICLR, 2021. URL httpp::/oppenerreww..ett/// id=Wi <d=Wi5kUNlgp) 5KUN1
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. net.
In ICLR, 2017.
Devin Kreuzer, Dominique Beaini, William Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. arXiv preprint arXiv:2106.033 100.0210 2021.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. IEEE Transactions Pattern Analysis and Machine Intelligence, 2021a.
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, pp. 10012-10022, 2021b.
Ze Liu, Jia Ning, Yue Cao, Yixuan Wei, Zheng Zhang, Stephen Lin, and Han Hu. Video swin transformer. arXiv preprint arXiv:2106. 13230, 2021c
Péter Mernyei and Cătälina Cangea. Wiki-cs: A wikipedia-based benchmark for graph neural networks. arXiv preprint arXiv:2007002901, 2020.
George A. Miller. WordNet: An electronic lexical database. Communications of the ACM, 38, 1995.
Erxue Min, Yu Rong, Tingyang Xu, Yatao Bian, Peilin Zhao, Junzhou Huang, Da Luo, Kangyi Lin, and Sophia Ananiadou. Masked transformer for neighhourhooodawware click-through rate prediction. arXiv preprint arXiv:2201. 13311, 2022.
Maho Nakata and Tomomi Shimazaki. Pubchemqe project: large-scale first-principles electronic structure database for data-driven chemistry. Journal of chemical information and modeling, 57(6): 1300-1308, 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. ICLR. OpenReview.net, 2020. URL /tttps://operrv
Roshan Rao, Jason Liu, Robert Verkuil, Joshua Meier, John F. Canny, Pieter Abbeel, Tom Sercu, and Alexander Rives. Msa transformer. bioRxiv. 2021. URL htttst:/ wwwww//wwww//w////////////w/www www..iv.oxiiooooooooo
content/10. 1101/20111111111111111 02. 12. 430858v1
11

---

Under review as a conference paper at ICLR 2023
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. arXiv preprint (ttv:1990.1102. 2019.
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, pp. 593-607, 2018.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günneeaann Pitfalls of graph neural network evaluation. arXiv preprint arXiv:181..05863 2018.
Zequn Sun, Chengming Wang, Wei Hu, Muhao Chen, Jian Dai, Wei Zhang, and Yuzhong Qu. Knowledge graph alignment network with gated multi-hop neighborhood aggregation. In AAAI, pp. 222-229, 2020.
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019. forum?id=HkqF@@me
nett/
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In CVSC, pp. 57-66, 2015,
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha P. Talukdar. Composition- multi- relational graph convolutional networks. In ICLR, 2020. URL http:ttt////ppneeeeeee..rr
Corum?id-Bie BA
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NIPS, pp. 5998-6008, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua
Bengio. Graph attention networks. In ICLR, 2018. URL http:///ppeneeveew..et
forum? dd=m:
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Improving graph attention networks with large margin-based constraints. CoRR, abs/1910.1 1945, 2019a.
Quan Wang, Pingping Huang, Haifeng Wang, Songtai Dai, Wenbin Jiang, Jing Liu, Yajuan Lyu, Yong Zhu, and Hua Wu. Coke: Contextualized knowledge graph embedding. arXiv preprint arXiv:1911.02166 2019b.
Ronald Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural computation, 1:243-248, 1989.
Yuting Wu, Xiao Liu, Yansong Feng. Zheng Wang, Rui Yan. and Dongyan Zhao. Relation-awar entity alignment for heterogeneous knowledge graphs. In IJCAI, pp. 5278-5284, 2019.
Hu Xu, Bing Liu, Lei Shu, and Philip S. Yu. BERT post-training for review reading comprehension and aspect-based sentiment analysis. In NAACL-HILT, pp. 2324-2335, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019b.
Wei Yang, Yuqing Xie, Aileen Lin, Xingyu Li, Luchen Tan, Kun Xiong, Ming Li, and Jimmy Lin. End-to-end open-domain question answering with bertserini. In NAACL-HLT, pp. 72-77, 2019.
Zhilin Yang. William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In JCML, volume 48, pp. 40-48, 2016.
Shaowei Yao, Tianming Wang, and Xiaojun Wan. Heterogeneous graph transformer for graph-to- sequente sequence learning. In ACL, pp. 7155-7154, 2020.
Semih Yavuz, Kazuma Hashimoto, Yingbo Zhou, Nitish Shirish Keskar, and Caiming Xiong. Model- ing multi-hop question answering as single sequence prediction. In ACL, pp. 974-990, 2022.
Rui Ye, Xin Li, Yujie Fang, Hongyu Zang, and Mingzhong Wang. A vectorized relational graph convolutional network for multi-relational network alignment. In IJCAL, pp. 4135-4141, 2019.
12

---

Under review as a conference paper at ICLR 2023
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? Thirty-Fifth Conference on Neural Information Processing Systems. 2021. URL https::/openreviee net/fooumm 1d=
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.
Cheng Zheng, Bo Zong, Wei Cheng. Dongjin Song, Jingehao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In ICML, volume 1 119, pp. 11458-11468, 2020.
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.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinform., 33(14):110-i199, 2017.
13

---

Under review as a conference paper at ICLR 2023
Table 7: The average training time of DET in comparison with respective basclines, on 32GB V100.
PCQMAM-LSCVI
ZINC
Cora
CiteSeer
FB15K-237
WNI8RR
Graphormer SuperGAT HinER
66h
30h
4m
6m
27h
DET
78h
4m
36h
Table 8: The dataset statistics. R and C' denote the regression and classification tasks, respectively.
POQMAM-LSCC1
ZINC
CiteSeer
PubMed
ogbn-arxxv
FB1SK-237
WNISRR
Graphs
3,803,453
12,000
24
# Nodes
53,814,542
277.920
2,708 5,429
3.327 4,732
19.717 44,338
56,944 818,716
169,343 1,166,243
14,951
40,943
# Edges
55,399,880
597.960
310,116
93,003
# Edge-type
237
# Task
R
18
# Classes
7
121
14,951
40,943
A POSITION EMBEDDING
There are many important graph features that can be used identify different nodes. Thanks to learnable position embedding, these discrete features now can be encoding into embeddings and combined with the raw nodes embedding vectors.
Specifically, for graph property prediction task, use the method proposed by Graphormer Ying ct al. 2021 to encode degree centrality an arbitrary node o; as follows:
C; = (deg(())))
where deg(n:) denotes the degree of the node and fe IR - T is the mapping function that converts the node degree to learnable embedding. We also consider encoding the distances from the node of interest to different neighbors by the following equation:
duy,y (spdd vy)),
(10)
where spd( vj) denotes the shortest path distance from v; to vj. and fa R R is similar function that converts the distance to a learnable embedding.
For KG representation learning task, follow (Chen al. (021b) encode the edge types into node embeddings, which is implemented by an additional atom triple Transformer M Specifically, for given triple (v,, Tijy Uz) for the node of interest u, where raj denote the edge type (i.e., relationship) between in and vy. The edge type information can be encoded by the following equation:
ei MM ([CA, Vz, Tig. V;l),
(11)
where |c Vi, Fij, vy] is the input embedding sequence. с is the virtual node for the atom Trans- former, whose output represents the edge encoding embedding.
B COMPUTATIONAL COST
We used one 32GB V100 GPU to train all the methods for estimation and show the average training time in Table Clearly, incorporating the semantic encoder did not significantly increase the computational cost, especially on the node classification datasets.
C EXPERIMENT DETAILS
C. DATASET SETTINGS
We present the overall dataset statistics in Table
14

---

Under review as a conference paper at ICLR 2023
Table 9: The hyper-parameter settings on the datasets the main experiments.
POQMAM-LSCC]
ZINC
Cora
CitcSoer
PubMed
PPI
ogbu-uradl
FB15K-237
WNIBRR
Learning-rate
0.0002
0. 0.00002
0.005
0.003
0.01
0.005
0.05
0.01
0 0.008
Batch-
256
256
128
128
128
128
126
512
512
Layer
Multi-hends
increasing
increasing
0.15
0.15
0.15
0.15
0.15
0.5
0.5
Semantic neighbors
16
16
50
Negative samples
50
0.5
062
Strun
Steara
0.14
0.2
18
10
222
1y0,000
310.000
18540
13.i0
785
(a) ZINC
(b) PCQM4M-LSCvI
Figure 5: The validate MAE ZINC and PCQMAM-LSCVI, w.r.t, training step.
Graph Property Prediction For PCQM4M-LSCv1. the model is asked to predict the DFT (density functional theory)-calculated HOMO-LUMO energy gap of given molecules. It contains than 3.8M 2D molecular graphs input, which is especially appropriate to evaluate the performance of model in large scale scenarios. On other hand, ZINC is relative small datasets, where the main target is to predict the graph property regression for constrained solubility. It is one of the most popular real-world molecular datasets for graph representation learning.
Node Classfication Cora, CiteSeer and PubMed are three citation network datasets proposed by (Yang al., 2016). They are typically used for transductive node classification task. PPI on the other hand is used for inductive evaluation. consists of 24 graphs, with 20 graphs for training, and 2 for validation and 2 for testing. All four datasets are the prevalent benchmarks used for node classification.
KG Completion FB15K-233 is the revised version of the original FB 1B15 dataset (Bordes et al. 2013) that was used as entity prediction benchmark in last ten years. However, recent stud- ies (Dettmers et al.) [0188] Toutanova & Chen 2015) find that the original FB15K contains large proportion redundant data, some of which may incur testing data leakage, the same to another well-used dataset WN18. Therefore, most latest studies only use the revised datasets FB15K -32 and WN18RR for evaluation. FB15K-237 has more different relationships, while WNISRR is more sparse and has more different entities.
C.2 PARAMETER SETTINGS
We summarize the main hyper-parameter settings on different datasets in Table The more specific settings can be found in the source code. For the graph property prediction tasks, we directly let the semantic encoder access all neighbors, and thus the semantic neighbor fetching loss is not used. Alternatively, we adapt an increasing strategy to gradually improve the weight of the output of semantic encoder during training.
15

---

Under review as a conference paper at ICLR 2023
Table 10: Accuracy on 8 popular node classification datasets.
Model
CS
Physics
Coru ML
Coru-Full
DBLP
Chameleon
Four Univ
Wiki-CS
GCN
91. 31.5_0.2 -.0.2
92.510
85.0
59.5
77.810.5
33.1
71820.6
71.021.0
GraphSAGE
90.0go.1
92.2
83.7 83.720.4
59.220.a
78.740.6
41.010.9
74.4go.6
77.5go.3
GAT
89.520.2
91 91.220.6
83.2 83.220.8
68.720.3
78.211.5
40.8
74.220.7
77.620.6
SuperGATSD
88.8+0.4
01.6+0.8
84.0+0..4
60.8+0.8
79.4+0..
41.6+0.7
76.2+0.8
77.9+0.7
DET
80.9
92.0
84.5
59.9
80.1
41.840.7
76.4=1.0
78.5=0.4
Table 11: A result comparison of different fx-
Methods
Cora
CiteSeer
PubMed
The proposed
84.6
72.8 72.3
81.8
Linear
83.3
80.2
D ADDITIONAL EXPERIMENTS
D.I ANALYSIS ON THE TRAINING PROCESS
We conducted experiments compare the performance of structural encoder with and without the semantic encoder, term of training steps.
We depict the valid MAE results on ZINC in Figure 5a At the beginning of the training, we find that the two methods do not have a visible performance gap. The curves are tightly overlapped during step 0 to 74, 000.
As the performance starts be converged, i.e., step 74, 000 to 148, 000, only using structural encoder is better than combining the two encoders. However, as the valid MAE tends to be stable, the dual-encoding DET gradually outperforms the single structural encoder.
It is worth-noting that the turning point appears at the performance starts to be converged, where the input embeddings also approach the ideal positions. Therefore, the semantic similarity among embeddings can be estimated more precisely, and contribute a better semantic encoder. Therefore, DET can obtain a lower MAE than the single strctural encoder. We present the result on PCQM4M- LSCvl in Figure 5b which supports the same conclusion.
D.2 RESULTS ON OTHER NODE CLASSIHICATION DATASETS
We also provide the results additional 8 real-world datasets for node classification. They are: CS and Physics (Shchur et al. 2018); Cora-ML, Cora-Full and DBLP (Bojchevski Günnemann) 2018): Chameleon (Rozemberezki al. 2019); Four- Univ (Craven et al. 1998); and Wiki-CS (Mernyei & Cangea 2020). We report the accuracy on Table [0] It is clear that DET consistently and significantly outperformed the attention-basse methods these datasets.
D.3 CHOICES OF ʃa
In this section, we conducted experiments to verify the effectiveness of proposed fa, in comparison with linear attention implementation. The results are shown in Table II we can observe that our proposed attention outperformed linear attention, and the results of using linear attention were similar to those of SuperGAT and the original GAT. SuperGAT also leverages self-supervised contrastive loss to predict the existence of edges in the original graph. If we use linear attention to replace our proposed attention, our method is more like a SuperGAT with two separated linear attentions to cope with node classification and edge prediction, respectively.
16


Reviews:
[{"review_id": "yiRtuFG7UY", "reviewer": "Reviewer_e1hj", "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 a new Graph Transformer architecture, named dual-encoding Transformer (DET), which has a structural encoder to aggregate information from near neighbors and a semantic encoder to focus on useful semantically close neighbors. The empirical results demonstrate that the proposed DET achieves superior performance compared to the respective state-of-the-art attention-based methods.", "summary_of_the_review": "The submission has thorough empirical results, but the empirical results do not look very competitive and the proposed method has only limited novelty", "strength_and_weaknesses": "strength:\n- The idea of disentangle and combine structural neighbors and semantic neighbors looks interesting to me.\n- The authors conducted thorough experiments on various datasets.\n\nweaknesses:\n- Some writing is a bit confusing. How to understand and interpret Figure 2? How do the authors define the semantic set $\\mathcal{N}^{\\text{se}}$? \"In our implementation, it is sampled from the top candidate\" what are the pool to select top candidates then? Is it all the other nodes?\n- What's the runtime analysis of the proposed method? How to understand Table 7? Why sometimes there's a nontrivial overhead and sometimes not?\n- The empirical performance of the proposed method is no longer the state-of-the-art performance. Please check [1]'s results on ZINC, for example. The authors should include and compare with this paper.\n\n[1] Dwivedi, Vijay Prakash, et al. \"Graph Neural Networks with Learnable Structural and Positional Representations.\" International Conference on Learning Representations. 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ig09pSYReg", "reviewer": "Reviewer_4oiv", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "The paper proposes Dual-Encoding Transformer (DET), which aggregates information from both local neighbors and semantically close neighbors to address the scalability issue of existing Transformer architectures for graphs. Also, the authors design self-supervised semantic neighbor fetching loss, which is jointly optimized with the main task loss.", "summary_of_the_review": "Overall, I am leaning towards rejection. My major concern is the novelty and experimental results. If you address my concerns, I will raise my score. ", "strength_and_weaknesses": "**Strengths**\n\n(1) This paper addresses the limitation of Transformer-based models for graphs, which is one of important topics to generalize Transformer to the graph domain.\n\n(2) The proposed DET shows the best performance on KG completion task.\n\n**Weakness**\n\n(1) I think that the novelty of this paper is limited. \n\n- The combination of structurally and semantically close neighbors has been already discussed in various works (Geom-GCN [1], Non-local GNNs [2]).\n- Also, semantic neighbor fetching loss seems similar to self-supervised loss of SuperGAT [3].\n\n(2) The accuracy of GCN and GraphSAGE on ogbn-arxiv is very low. From the leaderboard of ogbn-arxiv, the accuracy of GCN and GraphSAGE are 71.74 and 71.49, respectively. What makes deteriorating performance?\n\n(3) From Table 7, DET requires more average training time compared to Graphormer on PCQM4M-LSCv1 and ZINC datasets although DET uses less neighborhoods compared to Graphormer.\n\n(4) In Section 5.2, the paper discussed the correlation between semantic encoding and graph homophily. So, it would be better if the paper compare the performance on heterophilic graph datasets with baselines such as H2GCN [4].\n\n---\n\n[1] Pei, Hongbin, et al. \"Geom-gcn: Geometric graph convolutional networks.\" ICLR 2020.\n\n[2] Liu, Meng, Zhengyang Wang, and Shuiwang Ji. \"Non-local graph neural networks.\" TPAMI 2021.\n\n[3] Kim, Dongkwan, and Alice Oh. \"How to find your friendly neighborhood: Graph attention design with self-supervision.\" ICLR 2021.\n\n[4] Zhu, Jiong, et al. \"Beyond homophily in graph neural networks: Current limitations and effective designs.\" 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YY15Ey4vB_", "reviewer": "Reviewer_FttT", "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 proposes a novel graph transformer architecture that jointly aggregates structural neighbors and semantically related neighbors to encode each node. The proposed method is evaluated on various levels of graph learning tasks and confirmed to be effective.", "summary_of_the_review": "I think the proposed transformer architecture is somewhat novel to me. It is empirically evaluated in an extensive way, showing its effectiveness. Currently, I can only evaluate the behavior of semantic component based on the case shown in experiment, where the semantic neighbors seem to be truly semantically relevant. I don't have confidence to suggest an acceptance now, and more theoretical analysis would resolve my concerns.", "strength_and_weaknesses": "strengths:\n1. This paper studies a critical problem, that is to say, how to preserve the advantage of transformer to enjoy a large receptive field and, at the same time, efficiently aggregate discriminative information. In this regard, the contribution is likely to make a significant impact to the community.\n2. The proposed neural architecture is novel to me, which, instead of considering sparsity trick or hierarchical structure, directly defines neighborhood in the latent semantic space.\n3. The experiments are solid in terms of their comprehensiveness. Besides, the ablation studies confirm the effectiveness of introduced components. The case study of semantic neighbors also implies that the semantic encoder works with meaningful neighbors.\n\nweaknesses:\n1. It seems that there is a lack of theoretical analysis about the proposed architecture. I am really curious about what semantic similarities would be learned eventually. Meanwhile, what is the negative distribution should be adopted deserves a more detailed discussion, especially considering the number of examples increases along with the number of hops exponentially.", "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": "3J8HVWx4_i", "reviewer": "Reviewer_aSXN", "summary": "", "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": "", "summary_of_the_paper": "This work proposes DET, a transformer architecture for handling large graphs.\n\nDET relies on two attention mechanisms:\n- A structural attention mechanisms, i.e. for a given node, attention applied between a virtual global node and the neighboring nodes only. Moreover, a learnable position encoding is added (including centrality, distance to other neighbors and edge type).\n- A semantic attention mechanism, i.e. attention applied to semantic neighbors. More precisely, and for a given node, the other nodes are ranked depending on a learned embedding similarity score which is then used as an attention weight. This score can be learned via a self-supervised objective.\nAlthough computing the similarity score for each node has quadratic complexity in the number of nodes., the ranking step is done every few epochs only, providing an efficient attention mechanism in practice.\n\nThe authors then proceed to demonstrate the effectiveness of graph and node level tasks, with strong results for PCQM4M, ZINC, ogbn arxiv and knowledge graph completion. Finally, further studies of DET are provided: an ablation is done to understand the role of structural attention, semantic attention, and the semantic attention loss, a study on the usefulness of semantic encoding w.r.t. graph homophily, and an example of learned relations by the different mechanisms.\n", "summary_of_the_review": "This work offers a sensible solution to an important problem, with strong results. Although some elements could be clarified in the writing (novelty, more motivation for the virtual node in local attention and the SSL loss) and some ablation may be in my opinion missing, the pros outweight the cons and I tend to recommend acceptance.", "strength_and_weaknesses": "Strength:\n- This work offers a potential solution, DET, to an important problem, scaling transformers to large graphs.\n- The method is simple and motivated: a local attention scheme is augmented by an attention scheme that is able to fetch remote useful nodes. An SSL loss allows to learn the score used for ranking and attention weighting. Ranking only every few epochs seems to provide an efficient attention scheme in practice.\n- DET demonstrates strong results on various and important benchmark such as PMQC4M and ZINC.\n- This work studies in detail the proposed attention scheme and in particular the semantic attention: we see that the nodes fetched by the semantic encoder make sense, and that the semantic encoder is as expected useful when considering low homophily graphs.\n\nWeaknesses:\n- One novelty of this work, and what makes it scalable, is applying a custom attention to top ranked nodes, with an updated ranking every few epochs. In light of this, a natural baseline would be to apply linear attention instead of the proposed $f_s$: it would be more convincing to demonstrate the usefulness of $f_s$ compared to linear attention.\n- The other novelty is the use of a virtual node for a local attention mechanism. I am not sure to understand the motivation of this mechanism compared to a purely local attention scheme (attention between the node of interest and its neighbors): clarification and/or ablation could be useful to better understand the interest of the proposed scheme.", "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": {}}]

Author rebuttal:

Decision: Reject