Representing Long-Range Context for Graph Neural Networks with Global Attention
Authors: Zhanghao Wu
Paras Jain
Matthew A. Wright
Azalia Mirhoseini
Joseph E. Gonzalez
Ion Stoica
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural networks
transformers
long-range context
OpenGraphBenchmark

Abstract: Graph neural networks are powerful architectures for structured datasets. However, current methods struggle to represent long-range dependencies. Scaling the depth or width of GNNs is insufficient to broaden receptive fields as larger GNNs encounter optimization instabilities such as vanishing gradients and representation oversmoothing, while pooling-based approaches have yet to become as universally useful as in computer vision. In this work, we propose the use of Transformer-based self-attention to learn long-range pairwise relationships, with a novel “readout” mechanism to obtain a global graph embedding. Inspired by recent computer vision results that find position-invariant attention performant in learning long-range relationships, our method, which we call GraphTrans, applies a permutation-invariant Transformer module after a standard GNN module. This simple architecture leads to state-of-the-art results on several graph classification tasks, outperforming methods that explicitly encode graph structure. Our results suggest that purely-learning-based approaches without graph structure may be suitable for learning high-level, long-range relationships on graphs. Code for GraphTrans is available at https://github.com/ucbrise/graphtrans.

Representing Long-Range Context for Graph Neural Networks with Global Attention
Zhanghao Wu Paras Jain *1 Matthew Wright' Azalia Mirhoseini' Joseph E. Gonzalez', Ion Stoica' UC Berkeley, Google Brain Correspondence {zhwu, jarrs__jiinSbbrkeeee edu "quul contribution, determined via a random coin flip.
Abstract
Graph neural networks are powerful architectures for structured datasets. How- ever, current methods struggle to represent long-range dependencies. Scaling the depth or width of GNNs is insufficient to broaden receptive fields as larger GNNs encounter optimization instabilities such as vanishing gradients and rep- resentation oversmoothing, while pooling-based approaches have yet to become universally useful as in computer vision. In this work, we propose the use of Transformer-basee self-attention to learn long-range pairwise relationships, with novel "readout" mechanism obtain global graph embedding. Inspired by recent computer vision results that find position-inver invvariat attention performant learning long-range relationships, method, which call GraphTrans, applies a permutation-invariant Transformer module after a standard GNN module. This simple architecture leads state-of-the-ar results several graph classification tasks, outperforming methods that explicitly encode graph structure. Our results suggest that wweey-learning-bseee approaches without graph structure may be suitable for learning high-level, long-range relationships on graphs. Code for GraphTrans is available at https: // www.ttt......eeeeeeeeeeeeeteeeee www./oooomcceeeeeeee graphtrans.
Introduction
Graph neural networks (GNNs) enable deep networks process structured inputs such molecules social networks. GNNs learn mappings that compute representations at graph nodes and/or edges from the structure of and features in their neighborhoods. This neighborhood- aggregation leverages the relational inductive bias encoded by the graph's 's connectivity [3]. Similar to convolutional neural networks (CNNs), GNNs can aggregate information from beyond local neighborhoods by stacking layers, effectively broadening the GNN receptive field.
However, GNN performance drops dramatically when its depth increases [21]. This limitation has hurt the performance of GNNs on whole -raeee-raphh classification and regression tasks, where we want to predict target value describing the whole graph that may rely long-range dependencies that may not be captured by GNN with a limited receptive field [35]. Consider for example a large graph where node A must attend distant node B which is K-hops away. If our GNN layer aggregates only over a node's one-hop neighborhood. then a K K-layer GNN is required. However, the width of the receptive field of this GNN will grow exponentially, diluting the signal from node B. That is, simply expanding the receptive field to K-hop neighborhood may not capture these long-range dependencies either [40]. Often, "too deep" GNNs lead to node representations that collapse to be equivalent over the entire graph, a phenomenon sometimes called oversmoothing or oversquashing [21, 2]. Therefore, the maximum context size for common GNN architectures effectively limited.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Transformed <CLS>
<CLS>
with Global Info
Flatten
Transformer
Lineer
Concat
Embeddings Nodes
Graph
Embeddings
Figure 1: Architecture of GraphTrans. A standard GNN submodule learns local, short-range structure, then global Transformer submodule learns global, long-range relationships.
Several proposed methods combat the oversmoothing problem via intermediate pooling operations similar to those found today's CNNs. Graph pooling operations gradually coarsen the graph in progressive GNN layers, usually by collapsing neighborhoods into single nodes [9, 37, 20, etc.]. In theory, hierarchical coarsening should allow better long-range learning, both by reducing the distance information has travel and by filtering unimportant nodes. However, graph pooling operation has been found that as universally applicable as CNN pooling. State-of-the-aa results are often obtained with models using intermediate graph coarsening [27], and some results suggest neighborhood-looc coarsening may be unnecessary or counterproductive [23].
In this work, we take different approach at graph pooling and learning long-range dependencies in GNNs. Like hierarchical pooling, our method is also inspired by methods for computer vision: we replace some of the atomic operations that explicitly encode relevant relational inductive biases (i.e., convolutions or spatial pooling in CNNs, neighborhood coarsening in GNNs) with purely learned operations like attention [11, 4, 7].
Our method, which we call Graph Transformer (GraphTrans, see Fig. 1), adds a Transformer subnetwork top of a standard GNN layer stack. This Transformer subnetwork explicitly computes all pairwise node interactions a position-agnostic fashion. This approach intuitive as retains GNN specialized architecture to learn local representations of the structure of node's immediate neighborhood while leveraging the Transformer as a powerful global reasoning module. This parallels recent computer vision architectures, where authors have found hard relational inductive biases important for learning short-range patterns but less useful or even counterproductive in modeling range dependencies [25]. As the Transformer without positional encoding is permutation- invariant, we find it is a natural fit for graphs. Moreover, GraphTrans does not require any specialized modules architectures and can be implemented in any framework atop any existing GNN backbone.
We evaluate GraphTrans on variety of popular graph classification datasets. We find significant improvements in accuracy on OpenGraphhBenchmake [15] where achieve state-of-the-as results on two graph classification tasks. Moreover, we find substantial improvements on the molecular dataset NCII. Surprisingly, we find our simple model outperforms complex baselines for long-range modeling in graphs via hicrarchical clustering such as self-attention pooling [20].
Our contributions are as follows:
We show that long-range reasoning via Transformers improve graph neural network (GNN) ac- curacy, Our results suggest that modelling all pairwise node-node interactions in the graph is particularly important for large graph classification tasks.
We introduce a novel GNN "readout module." Inspired by text-classification applications of Transformers, we use a special "<CLs>" token whose output embedding aggregates all pairwise interactions into single classification vector. We find that this approach outperforms both non-learned readout methods like global pooling as well as learned aggregation methods like graph-specific pooling methods [37, 20] and "virtual node" approaches.
Using our novel architecture GraphTrans, we obtain state-of-the-ee results on several OpenGraph- Benchmark [15] datasets and the NCI biomolecular datasets [30].

---

2 Related Work
Graph Classification. Graph classification is an important task in real-world applications. Though GNNs encode the structured data into the node representations, aggregation of the representations to single graph embedding for graph classification still a problem. Similar CNNs, pooling in GNNs can be either global, reducing a set of node and/or edge encodings to single graph encoding, or local, collapsing subsets of nodes and/or edges to create a coarser graph. Paralleling the use of intermediate pooling within CNNs, several authors have proposed local pooling operations meant to be used within the GNN layer stack, progressively coarsening the graph. Methods proposed include both learned pooling schemes [37, 20, 14, 16, 1, etc.] and non-learned pooling methods based on classic graph coarsening schemes [10, 9, etc. However, the effectiveness or necessity of hierarchical, coarsening- baaeedding- pooling in GNNs is unclear [23]. On the other hand, the most common global, whole-graph pooling methods, are i) non-learned mean or max max--oooingg over nodes and ii) the "virtual node" approach, where a final GNN layer outputs an embedding for single virtual node that is connected to every "real" node in the graph.
A notable work related to graph pooling is the DAGNN (Directed Acyclic Graph Neural Network) of Thost and Chen [27], which had obtained the previous state-of-the-an accuracy on The DAGNN layer aggregates over the entire graph within each layer via an RNN that traverses the DAG, unlike most GNN layers that only aggregate over a node's s neighborhood. While they did not characterize this method as a pooling operation, it is similar to GraphTrans in that it acts as learned global pooling (in that it aggregates the embeddings of every node in a DAG into the sink nodes) that can model long-range dependencies. Note that GraphTrans is also complementary to DAGNN because their final graph-level pooling operation is global max-pooling over the sink nodes rather than learned operation.
Transformers on Graphs. Several authors have investigated applications of Transformer architec- tures to graphs. Recent works such as Zhang et al. [38], Rong et al. [24], and Dwivedi and Bresson [12] propose GNN layers that let nodes attend to other nodes in some surrounding neighborhood via Transformer-style attention, whereas we use self attention for a permutation invvrrinntn,, graph-level pooling or "readout" operation that collapses node encodings to a single graph encoding. Of these, Zhang et al. [38] and Rong et al. [24] tackle the problem of learning long-range dependencies without over smoothing by allowing nodes to attend to more than just the one-hop neighborhood: Zhang et al. [38] take the attended neighborhood radius as a tuning parameter and Rong et al. [24] attend to neighborhoods of random size during training and inference. In contrast, we use whole- graph self-attention allow for learning of long-range dependencies.
While Zhang et al. [38] do not consider whole-graph prediction problems, in the case of Dwivedi needed for graph classification regression, they used global average pooling over the nodes, while Rong et al. [24] take a weighted sum over nodes with the weights computed bypassing the h to a two-layer MLP. Note also that prior works consider graph-specific versions of a Transformer's positional encoding, while we omit positional encodings ensure permutation invariance.
and Bresson [12], when graph-wide embedding
Efficient Transformers. Transformer [28) has been widely used in sequence modeling. Recently, modifications of the transformer architecture emerge to further improve the efficiency [34, 19, 6]. The Literranffrrmrr [34] with less FLOPs, Reformer [19] with complexity, and Performer [6] with both less computation and memory complexity. Neural architecture search (NAS) was also applied to Transformer to fulfill the resource constraints for the edge devices [32]. These off-th architectures are orthogonal to our GraphTrans and can be adopted to improve the scalability.
3 Motivation: Modeling Long-Range Pairwise Interactions
To summarize, attempting long-range learning on graphs via stacking GNN layers or hierarchical pooling have not yet led to performance increases, and while some works have shown some success in expanding the receptive field of a single GNN layer beyond a one-hop neighborhood [38, 24, 40), it remains to be seen how this approach will scale very large graphs with thousands of nodes.
An inspiration for an alternative approach can found the recent computer vision literature. In the last few years, researchers have found that attention mechanisms act drop-in replacements
3

---

1 2
4 5
901112311411511111
0.30
0.25
10
0.15
10-
0..0
13
16
0.00
(a) Example graph from Code2.
(b) Corresponding attention map from GraphTrans.
Figure 2: Example graph and attention map in our GraphTrans. The graph is randomly sampled from the Code2 validation set. The attention map is retrieved from the first layer of the transformer module in our GraphTrans. The horizontal axis corresponds corresponds to sources (so, attention weights will sum to one over the horizontal axis). Note that in (b), index 18 corresponds the special <CLS> token described in section
targets and the horizontal axis
for traditional CNN convolutions [4, 7]: attention layers lear to reproduce the strong relational inductive biases induced by local convolutions. More recently, state-of-th sfate-of-the-an art approaches to several computer vision tasks etc.J. These results suggest that while strong relational inductive biases are helpful for learning local, short-range correlations, for long-range correlations less structured modules may be preferred [2].
attention-style submodule top of traditional CNN backbone [2, 33,
We leverage this insight to the graph learning domain with our GraphTrans model, which uses traditional GNN subnetwork
backbone, but leaves learning long-range dependencies Transformer subnetwork with no graph spatial priors. As mentioned, our Transformer application lets every node attend to every other node (unlike other approaches of applying Transformers to graphs that only allow attention to neighborhoods), which incentivizes the Transformer to learn the most important mode-node relationships, instead of favoring nearby nodes (the latter task having been offloaded to the preceding GNN module).
Qualitatively, this scheme provides evidence that long-range relationships are indeed important. An example application GraphTrans on the OGB Code2 dataset depicted Figure In this task, we take in the Abstract Sentence Tree obtained by parsing a Python method and need to predict the tokens that form the method name. The attention map exhibits similar patterns to those found in NLP applications of Transformers: some nodes receive significant weighting from many other nodes, regardless the distance between them. Note that node 17 assigns significant importance to node despite these two nodes being five hops away. Also, in Figure 2's attention map, index 18 refers to the embedding corresponding to the special <CLS> token we use as a readout mechanism, described in more detail below. We allow this embedding to be learnable, (represented by the many dark cells in column 18) may suggest these nodes are obtaining some graph- general memory from the learned embedding. This qualitative visualization, along with our state-of-the-aa results, suggest that removing spatial priors when learning long-range dependencies may be necessary for effective graph summarization.
the many nodes attending it
4 Learning Global Information with GraphTrans
Referring back to Figure 1, GraphTrans consists of two primary modules: GNN subnetwork followed by Transformer subnetwork. We discuss these in detail next.
GNN module. We consider graph property prediction, i.e., for each graph G = (V,E) we have graph-specific prediction target yg. We suppose that each node v V has an initial feature vector h e dR As GraphTrans is generally-applicall framework that can be used in concert with

---

variety of GNNs, we make very few assumptions on the GNN layers that feed into the Transformer subnetwork. generic GNN layer stack can be expressed as
h = fe (hr 1- (ha u E ((o))) - 1
(1)
where LGNN is the total number of GNN layers, S V is some neighborhood of v, and fe(-) is some function parameterized by neural network. Note that many GNN layers admit edge features, but to avoid notational clutter we omit discussion of them here.
Transformer module. Once we have the final per-node GNN encodings fe we pass these to DraphTrans's 's Transformer subnetwork. The Transformer subnetwork operates as follows. We first perform linear projection of the h L.aas's to the Transformer dimension and a Layer Normalization to normalize the embedding:
h LayerNorm W pt
where WPnij E
is a learnable weight matrix, and dIF and dLow are the Transformer dimension and the dimension of the final GNN embedding, respectively. The projected node embeddings hg are then fed into standard Transformer layer stack, with additive positional embeddings, as we expect the GNN to have already encoded the structural information into the node embeddings:
G = (W
(W,
1/V
du
a = softmax (d),.))
WEV
R = Σ
u W K
WEV
where W.. W.K. wy E R Xdys/ are the learned query, key, and value matrices, respec- tively, for a single attention head in layer l. As standard, we run Thead parallel attention heads and concatenate the resulting per-head encodings h. Concatenated encodings are then passed to Transformer fully-connected subnetwork, consisting of the standard Dropout + Layer Norm - FC - nonlinearity > Dropout - FC Dropout + Layer Norm sequence, with residual connections from h after the first dropout, and from before the first fully-connected sublayer after the dropout immediately following the second fully-comnected sublayer.
<CLS> embedding as GNN "readout" method. As mentioned, for whole-graph classification we require a single embedding vector that describes the whole graph. In the GNN literature, this module that collapses embeddings for every node and/or edge to a single embedding is called the "readout" module, and the most common readout modules are simple mean or max pooling, or single "virtual node" that is connected to every other node in the network.
In this work, we propose a special-token readout module similar to those used in other applications of Transformers. In text classification tasks with Transformers, a common practice is append special <CLS> token to the input sequence before passing it into the network, then to take the output embedding corresponding to this token's position as the representation of the whole sentence. In that way. the Transformer will be trained to aggregate information of the sentence to that embedding, by calculating the one-to-one relationships between the <CLS> token and each other tokens in the sentence with the attention module.
Our application of special- token readout is similar this. Concretely, when feeding the transformed per-node embeddings TC, we append an additional learnable emhedding heasss to the sequence, and take the first embedding hecus>> Rd from the transformer output as the representation of the whole graph (note that since we do not include positional encodings, placing the special token at the "beginning" of the sentence has no special computational meaning; the location is chosen by convention). Finally, we apply linear projection followed by softmax generate the prediction:
y = softmax (Wour T hectss)
where LTF is the number of Transformer layers.
This special-token readout mechanism may viewed as generalization or a "deep" version of virtual node readout. While virtual node method requires every node in the graph to send its
5

---

information to the virtual node and does not allow for learning pairwise relationships between graph nodes except within the virtual node's embedding (possibly creating an information bottleneck). a Transformer-style special-token readout method lets the network learn long- long-range node-to-node relationships in earlier layers before needing to distill them in the later layers.
5
Experiments
We evaluate GraphTrans on graph classification tasks from three modalities: biology, computer programming, and chemistry. Our GraphTrans achieves consistent improvement over all of these benchmarks, indicating the generality and effectivvness of the framework. All of our models are trained with the Adam optimizer [17] with learning rate of 0.0001, a weight decay 0.0001, and the default Adam parameters. All Transformer modules used in our experiments have an embedding dimension dur of 128 and a hidden dimension of 512 in the feedforward subnetwork. The Transformer baselines described below are trained with only the sequence of node embeddings, discarding the graph structure.
5.1 Biological benchmarks
We choose two commonly used graph classification benchmarks, NCI1 and NCT109 [31]. Each of them contains about 4000 graphs with around 30 nodes on average, representing biochemical compounds. The task is to predict whether compound contains anti-lung-cancer activity. We follow the settings [20, 2] for the NCI1 and NC1109, randomly splitting the dataset into training, validation, and test set by ratio of 8:1:1.
Datasets.
Training Setup. We trained GraphTrans both the NCI1 and NCI109 datasets for 100 epochs with batch size of 256. We run each experiment 20 times with different random seeds and calculate the average and standard deviation of the test accuracies. All the model follows the architecture in Figure 1, with transformer layers and a dropout ratio of 0.1 for both the GNN and Transformer modules. We two different settings adopted from prior literature for the width and depth of the GNN submodule in GraphTrans. The GNN module width and depth in the small TraphTrans model are copied from the simple baseline, i.e. the settings [20]. which has hidden dimension of 128 and 3 GNN layers. The settings of the GNN module in the large GraphTrans model are adopted from the default GCN/GIN model provided by OGB, which has a hidden dimension of 300 and GNN layers. We also adopt cosine annealing schedule [22] for learning rate decay.
Results. We report the results on both NCII and NCT109 in Table 1. The simple baselines, including GCN Set2Set, SortPool, and SAGPool, are taken from [20], while the strong baselines [13], as well as the FA layer [2]. In Table 1, Our Graph Transformer (small) has the same architecture as the simple baseline but improves the average accuracy by 7.1% for NCII and 5. 1% for NCT109. We also tested the framework with GIN as the encoder (CraphTrans (large)) to align with the settings in the strong baseline, which also significantly improves the accuracy of the strong baseline by 1. for NCII and the 8.2% for NCI109, even without the deep GNN, using 4 layers instead of 8.
5.2 Chemical benchmarks
Datasets. For chemical benchmarks, we evaluate GraphTrans dataset larger than NCI dataset, molpcba from the Open Graph Benchmark (OGB) [15]. It contains 437929 graphs with 28 nodes on average. Each graph in the dataset represents molecule, where nodes and edges are atoms and chemical bonds, respectively. The task is to predict the multiple properties of molecule, We use the standard splitting from the benchmark. The performance on the GIN and GIN-Virtus baselines are reported on the OGB leaderboard [15].
Training Setups. All the GNN modules in the experiments follow the settings of the default GIN model provided in OGB, with 4 layers and 300 hidden dimension. We train all the models for 100 epochs with a batch size of 256 and report the test result with the best validation ROC-AUC. For both GNN and Transformer modules, we apply a dropout of 0.3. We use GIN as the baseline and the GNN module, since it performs better than GCN models on the Molpeba dataset.

---

Table 1: NCT biological datasets GraphTrans outperforms past baselines on both NCII and NCI109 test accuracy while using fewer GNN layers than prior SOTA baselines.
Model
GNN Type
GNN layer count
NCI1 (%)
NCI109 (%)
Set2Set [29, 20]
GCN
68.6 1.9
69.8
SortPool [39, 20]
GCN
1..
74.0#
SAGPool,, [20]
GCN
67.5+1.1
67.9
SAGPool, [20]
GCN
7..2
74.1
Errica et al. [13]
GIN
80,0
Alon and Yahav [2]
GIN
81.5+1.2
Transformer [28]
68.512..6
70.1 2.3
GraphTrans (small)
GCN
81.31119
79.2:1.22
GraphTrans (large)
GIN
82.61:1.2
82.3
Table 2: OpenGraphBenchmark Molpcha dataset Overall, GraphTrans outperforms competitive baselines with two backbone GNN architectures.
Model
Valid ROC-AUC
Test ROC-AUC
GCN [18]
0,2059 0.2305::0.0027
0,2020=0.0024
GIN [36]
0.226610.0028
GCN-Virtual [18]
0.2495++0.0047
0.2424+000033
GIN- Virtual [36]
0.2095
0.2703++0.0023
Transformer [28]
0.1316::0.0012
0.1281+:0.0039
GraphTrans (GIN)
0.2093+00.050 0.2867+:0.002
0.2756+00.003
GraphTrans (GIN-Virtual)
0.2761:0.0029
Results. In Table 2, we report the ROC-AUC on validation and test set of Molpcba. Though Transformer alone works very badly on this dataset, our GraphTrans still improves the ROC-AUC of the GIN and GIN-Virtual bascline. indicates that our design could take benefit from both the local graph structure learned by the GNN and the long-range concept retrieved by the Transformer module based on the GNN embeddings.
5.3 Computer programming benchmark
Datasets. For the computer programming benchmark, we also adopt large dataset, code2 from OGB, which has 45741 graphs each with 125 nodes average. The dataset is collection of Abstract Syntax Trees (ASTss) from about 450k Python method definitions. The task to predict the sub-tokens forming the method name, given the method body represented by the AST. We also adopt standard dataset splitting from the benchmark. All baseline performances are as reported on OGB leaderboard.
Training Setups. We also apply the default settings of GCN for Code2 from OGB, with 4 GNN layers, 300 hidden dimension, and a dropout ratio of 0.0. We apply a dropout ratio 0.3 to the Transformer module to avoid overfitting. We train all the models for 30 epochs with batch size of 16, due to the large scale of the dataset. For the GraphTrans (PNA) model, we follow the settings in [26), with a hidden embedding of 272 for the GNN module and weight decay of 3e-6. The only difference is that we still use the learning rate 0.0001, instead of the heavily tuned 0.00063096 [26]. We run each experiment 5 times and take the average and standard deviation of the Fl score.
Results. In Table 3, compare our GraphTrans with top tier architectures the leaderboard on Code2 dataset. As the average number of nodes each graph increases, the global information becomes more important it becomes more difficult for the GNN gather information from
7

---

Table 3: OpenGraphBeechhark Code2 dataset All the baselines are collected from the OGB leaderboard. GraphTrans outperforms the of DAGNN. The improvement based on PNA model indicates that our method is orthogonal to the type of GNN module.
Model
Valid F1 score
Test score
GIN [36]
0.1376=0.0016
0.1495#0.0023
GCN [18]
0.1399=0.0017
0.1507=0.0018
GIN-Virtual [36]
0.1439=0.0026
0.1581#0.0020
GCN-Virtual [18]
0.1461 +0.0011
0.1595+000008
PNA [8]
0.1453++0.002
0.1570+0.0032
DAGNN (SOTA) [27)
0.1607=+0.000
0.1751#0.0049
Transformer [28]
0.1546+0.0018
0.1670=H0.0015
GraphTrans (GCN)
0.159910.0009
0.1751#0.0015
GraphTrans (PNA)
0.1622=0.0025 0.1661=0.0012
0.1765=0.0033
GraphTrans (Crttuir
0.1830=0.0024
Table 4: Ablation of Transformer module On the Code2 dataset, only training the Transformer module in GraphTrans with a frozen pre-trained GNN module also improves the Fi-score. It indicates that training the Transformer on GNN embeddings can learn information that is not captured by the GNN.
Model
Valid F1 score
Test F1 score
Pre-trained GCN-Virtual
0.1457
0.1574
GraphTrans, pre-trained GCN-Virtual frozen GNN
0. 1479
0.1616
GraphTrans, pre-trained GCN-Virtual fine-tuned GNN
0.1564
0.1733
nodes far away. Even without heavy tuning, GraphTrans significantly outperforms the state-of- the-art (DAGNN) [27] on the leaderboard. We also include the results for the PNA model and our GraphTrans with the PNA model as the GNN encoder. Our GraphTrans also significantly improves the result, which indicates that our architecture orthogonal to the variants of the GNN encoder module.
5.4 Transformers can capture long-range relationships
As we previously observed Figure 2 and discussed in Section the attention inside the transformer module can capture long-range information that is hard to be learned by the GNN module.
To further verify the hypothesis, designed an experiment to show that the Transformer module can learn additional information to the GNN module. In Table 4, we first pretrain GNN Virtual) until converge on the Code2 dataset, and then freeze the GNN model and plug our Transformer module after it. By training the model on the training set with fixed GNN module, we can still observe 0.0022 Fi-score improvement on validation set and 0.0042 on test set. It indicates that the Transformer can learn additional information that is hard to be learned by the GNN module along.
With pretrained and unfrozen GNN module, our GraphTram can achieve even higher Fl-score. That may because the GNN module can now focus on learning the local structure information, by leaving the long-range information learning the Transformer layer after it. The model benefits from the specialization as mentioned in [34]. Note that for all the experiments in Table 4, we do not concatenate the embeddings from the input graph to the input of Transformer for simplicity.
5.5 Effectiveness of <CLS> embedding
In Figure 2b, we can observe that row 18 (the last row is for <CLS>) has dark red multiple columns, which indicates that the <CLS> learns to attend important nodes in the graph to learn the representation for the whole graph.
8

---

Table 5: Ablation of <CLS> token The mean and last are two commonly used embedding
aggregation method for sequence classification.
Model
Valid
Test
GraphTrans, mean
0.1398
0.1509
GraphTrans, last
0.1566
0.1716
GraphTrans, <CLS>
0.1593
0.1784
GraphTrans, <CLS>, cat
0.1670
0.1810
Table 6: Scalability of Transformer to large graphs We profile our Code2 model random graphs and list runtime in milliseconds. GraphTrans scales comparably to the GCN model due to the high cost neighbor sampling in GNN training. With graphs over 1000 nodes, GraphTrans is no less scalable than the GCN baseline.
Edge Density
Node count
Model
20%
40%
60%
80%
GCN- [18]
44.3
58.5
79.3
99.0
500
GraphTrans (GCN)
48.4
57.5
76.4
93.7
GCN-Virtull [18]
99.1
171.8
249.5
OOM
1000
GraphTrans (GCN)
96.9
168.4
244.3
OOM
GCN-Virtual [18]
131.8
237.7
OOM OOM
OOM
1200
GraphTrans (GCN)
127.9
236.6
OOM
We also examined the effectiveness of our <CLS> embedding quantitatively. In Table 5, we tested several common methods to for sequence classification. The mean operation averages the output single graph embedding: the last operation takes the last
embeddings of the transformer embedding in the output sequence as the graph embedding. The quantitative results indicate that the <CLS> embedding is most effective with 0.0275 improvements the test set, as the model can learn to retrieve information from different nodes and aggregate them into one embedding. The concatenation of the embeddings in the input graph and the input embeddings of the transformer can further improve the validation and test F1-score to 0. 1670 and 0. 0733.
5.6 Scalability
To quantitatively benchmark how GraphTrans scales with large graphs over 100 nodes, we ran microbenchmark of iteration time for training with varying graph size and edge density. We train baselines on randomly generated Erdos-Renyi graphs with varying number of nodes and edge density. As shown in the Table 6, our GraphTrans model scales at least as well as the GCN model when the number of nodes and edge density increases. Both GCN and GraphTrans see of memory errors (OOM) with large dense graphs, but we note that GraphTrans had similar memory consumption to the GCN baseline.
5.7 Computational efficiency
To evaluate the overhead that our GraphTrans adds over a specific GNN backbone, we evaluate the forward pass runtime and backward pass runtime per iteration. We normalize models to have roughly similar parameter counts. The results are shown in Table 7. For the NCI1 dataset, GraphTrans actually faster to train than a comparable GCN model. For the OGB-molpeha and OGB-Code2 datasets, GraphTrans is 7-11% % slower than the baseline GNN architectures.
5.8 Number of parameters
We compare the number of parameters of the GNN baseline and the GraphTrans on different dataset in Table 8. Overall, GraphTrans only increases total parameters marginally for Molpcba and NCL

---

Table 7: Speedup Transformer module For GraphTrans models trained over the NCII, OGBG- Molpeba and OGBG-Codes datasets, we find that the Transformer module adds minimal overhead. Speedup the training iteration speed compared to GNN based model; larger number indicates faster running speed.
Dataset
Method
Forward time (ms)
Backward time (ms)
Speedup
GCN-Virtual [18]
22.27 + 2.04
14.35 + 2.46
1.00
NCII
Transformer
12.31 + 1.68
9.32 + 1.68
1.69
GraphTrans
15.01 = 1.63
12.04 + 2.25
1.35x
GCN-Virtul [18]
14.79 + 2.54
12.75 # 3.00
1.00
Molpeba
Transformer
12.34 + 1.43
10.52 + 1.60
1.20
GraphTrans
16.55 + 2.93
14.3
0.89
VCrtViitual [18]
22.97 + 6.13
38.53 + 6.92
1.00
Code2
Transformer
31.01 + 9.00
33.30 + 16.09
0.96
GraphTrans
34.93 + 6.85
31.14 + 12.90
0.93x
Table 8: Parameter count Overall, GraphTrans achieves improved accuracy with a minor increase
in parameters.
Dataset
GNN
GraphTrans
Delta
Molpcba
3.4M
4.2M
0.8M
NCI
0.4M
0.5M
0.1M
Code2
12.5M
9.1M
-3.4M
For Code2, GraphTrans is substantially more parameter-efficien than the GNN while improving test F1 score from O. 0.19 to 0.1810. One reason for improved parameter efficiency is that the Transformer reduces feature dimension before the expensive final prediction layer.
6 Conclusion
We proposed GraphTrans, a simple yet powerful framework for learning long-range relationships with GNNs. Leveraging recent results that suggest structural priors may be unnecessary counterproductive for high-level, long-range relationships, we augment standard GNN layer stacks with subsequent permutation-invariin Transformer module. The Transformer module acts novel GNN "readout" module, simultaneously allowing the learning of pairwise interactions between graph nodes and summarizing them into special token's embedding as is done in common NLP applications of Transformers. This simple framework leads to surprising improvements upon the state of the art in several graph classification tasks across program analysis, molecules and protein association networks. In some cases, GraphTrans outperforms methods that attempt to encode domain-specific structural information. Overall, GraphTrans presents simple yet general approach to improve long-range graph classification; next directions include applications to node and edge classification tasks well further scalability improvements of the Transformer large graphs
7 Acknowledgements
We thank Ethan Mehta, Azade Nazi, Daniel Rothschild, Adnan Sherif and Justin Wong for thoughtful discussions and feedback. In addition to NSF CISE Expeditions Award CCF-1730628, this research is supported by gifts from Amazon Web Services, Group, Eriesson, Facebook, Futurewei. Google, Intel, Microsoft, Scotiabank, and VMware.
10

---

References
[1] A. H. K. Ahmadi, K. Hassani, P. Moradi, L.. Lee, and Q. Morris. Memory-based graph networks. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://openreviiee net/forum? ierrmmmmddrllaaeBBPP
[2] U. Alon and E. Yahav, On the bottleneck of graph neural networks and its practical implica- tions. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL id 1d=1800Ph0CVH2.
wtwpa/rwwwwiii.eeeoreoeeeee wwt. net/forum?
[3] W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalee
Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, C. Gulcehre, F. Song, A. Ballard, J. Gilmer, G. Dahl, Vaswani, K. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu. Relational inductive biases, deep learning, and graph networks. ArXiv preprint, abs/1806.01 2018. URL https: //te:////arii /awxiv...vv///////////a////aaa org/abs/ 1806. 01261.
[4] N. Carion, F. Massa, G. Synnaeve, N. Usunier, A. Kirillov, and S. Zagoruyko. End-to-End Object Detection with Transformers. ArXiv preprint, 12872, 2020. URL https: // //arxivv... org/ werg//bs//at abs/2005. 12872.
[5] D. Chen, Y. Lin, W. Li, P. Li, J. Zhou, and X. Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topologiaal view. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 3438-3445, AAAI Press, 2020. URL https: //waa/aaaaaa/aaaa/aaaa/aaaaaaa org/ojs/ heiis//ind..////eeeeee php/ AAAI/ articlevviex/57/
[6] K. M. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlós, P. Hawkins, J. Q. Davis, A. Mohiuddin, L. Kaiser, D. B. Belanger, L. J. Colwell, and A. Weller. Rethinking attention with performers. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https: /openreview
[7] Cordonnier, Loukas, and M. Jaggi. the relationship between self-attention and convolutional layers. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:// openreview
[8] G. Corso, L. Cavalleri, D. Beaini, Liò, and Velickovic. Principal neighbourhood aggregation for graph nets. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12. 2020, virtual, 2020. URL https: https:/ wtw.rooeeiinnnnn..iirr...oo neurins. courrps..c/pappe.. htte//pppe/222///eeeeeee ctattrract.ttm.l.
[9] M. Defferrard, X. Bresson, and Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In D. D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3837-3845, 2016. URL httpps//prroeeedingss newriss.e.i.pp... cc/ httpp/aapp/p///eeeeeee 1ee65- 1ee.eeffeeeeeee-eeeea-eeeeeee Abstract. html.
[10] I. S. Dhillon, Y. Guan, and B. Kulis. Weighted Graph Cuts without Eigenvectors A Multilevel Approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(1 (0(11))1944 1):1444-1955, 2007. ISSN 0162-8828. doi: (0.1109/TPAM..2007..1
[11] A. Dosovitskiy, L.. Beyer, Kolesnikov, D. Weissenborn, Zhai, Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x16
11

---

words: Transformers for image recognition at scale. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URI. https:://peerreeeee www..netooomddd-w.coooae...
[12] V. P. Dwivedi and X. Bresson. Generalization of Transformer Networks Graphs, ArXiv preprint, 2.0999,, 2020. URL
wwwpaaiwwww...a/////a/aaaa/ 09699.
[13] F. Errica, M. Podda, D. Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:/ / openreview net/forumiiddHyyDD HdFHgGE
[14] H. Gao and S. Ji. Graph u-nets. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Reseurch, pages PMLR, 2019. URL http: attp://prroceedings. mmr.
arres//v9/gaa0 htt.://n.....l...ee/ee/////////e
html.
[15] W. Hu, M. Fey, M. Zitnik. Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 12, 2020, virtual, 2020. URL https: httptthtt///oeeeeeee p/tpc//eeoccceesss/e/oeee neur ctt http//apprrr///// 2aaee//222///ha// /hash/ fb60d411a5c5B0 2B0004111cccb2222277777777888883
Awsr---ttttttttttee.eee html.
[16]
J. Huang, Z. Li, N. Li, S. Liu, and G. Li. Attpool: Towards hierarchical feature representation in graph convolutional networks via attention mechanism. In 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 -November 2, 2019, pages 6479 6488. IEEE, 2019. doi: 10.100//CCV222210000055 URL https://doi. org/10. 1.000.1100 1109 /CCVV 20....01..... 00658.
[17] D. P. Kingma and Ba. Adam: A method for stochastic optimization. In Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015. URL http: //arxiv.ors www.oogg///oooooooooooooooooooet abs//412. 6980.
[18] N. Kipf et al. Keras-GCN. https://iitubb.om//////////tt
2017.
[19] N. Kitaev, L. Kaiser, and A. Levskaya Reformer: The efficient transformer. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:://ppenrviieee wwt.//orunn..deerggttttttt
[20] J. Lee, Lee, and J. Kang. Self-attention graph pooling. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3734-3743, PMLR, 2019. URL http://proceedeeee http///rrceeen...c///////// 1ee19c.
.ml.. mml. prw.s/vspt
[21] Q. Li, Z. Han, and X. Wu. Deeper insights into graph convolutional networks for semi- supervised learning. S. A. Mellraith and K. Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3538-3545. AAAI Press, 2018. URL https: //s::///wwe //tw://wwww...o aaai org/ org//cc//e index. hAp/AAAT/AAATI8// BAAAA///AAAIB///ppp//r///s/////
[22] I. Loshchilov and F. Hutter. SGDR: stochastic gradient descent with warm restarts. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: //tp://v//e/er.eeeee wff.rrmmmddSk@999
[23] D. P. Mesquita, H. Jr. and Kaski. Rethinking pooling graph neu- ral networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin,
12

---

editors, Advances in Neural Information Processing Systems 33: Annual Confer- ence on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URI. https://prooeeddings www.neuriss.. courips.cc... wwtpe/pppee/////aaa/a/eeee
(0044BBee00117222e553332222 -tw.:eaabbdaaa---baaaratt.. Abstract.
[24] Y. Rong. Bian, T. Xu, W. Xie, Y. Wei, W. Huang, and J. Huang. Self-supervised graph transformer on large-scale molecular data. In H. Larochelle, M. Ranzato, R. Hadsell, M. Bal- can, and H. Lin, editors, Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12. 2020, virtual, 2020. URL httttp::/pproeedinngg neurips cc/ wwcp/pppp//000000 hatee////////hhh///// Awstract.
[25] A. Srinivas, T.-Y. Lin, N. Parmar, J. Shlens, P. Abbeel, and A. Vaswani. Bottleneck Transformers for Visual Recognition. ArXiv preprint, abs/2101.11605, 2021. URL hattps://arat org/ abs/2101 11605.
[26] S. A. Tailor, F. L. Opolka, P. Liò, and N. D. Lane. Adaptive filters and aggregator fusion for efficient graph convolutions. ArXiv preprint, abs/2104.01481, 2021. URL pettps://arxiz org/abat 2abbs2104.... 01481.
[27] V. Thost and J. Chen. Directed acyclic graph neural networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https: http::///opeeevveeeeeeeeee net//forum/iddDDaaF4333/
[28] A. Vaswani. N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polo- sukhin. Attention is all you need. In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fer- gus, V. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA. USA, pages 5998 6008, 2017. URL httpt:pp:pppccoceedaeeee mew.eeedinnnn..uuip..... neurips. cc/ cc/paper/o / /017 htah//ash//aa//aaa httas///f.eeeeeeeeeeefsssseseee. -steeeeeeerrrooccccccaeaaaaaaaee www.aaattttttttttta.aaaaaa..e.ea html.
[29] O. Vinyals, S. Bengio, and M. Kudlur. Order matters: Sequence to sequence for sets. In Bengio and Y. LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL wrt. http///bbb/111........
[30] N. Wale and G. Karypis. Comparison of Descriptor Spaces for Chemical Compound Retrieval and Classification. In Sixth International Conference Data Mining (CCMM'06), pages 2006. doi: 10110//CMM.20006.999
[31] N. Wale, I. A. Watson, and G. Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008 ISSN 0219-3116. doi: 10.1007/1101155007-000000 110115-007-0103-11
URL https: //ooi. org/10..
[32] H. Wang. Z. Wu, 7. Liu, H. Cai, L. Zhu, C. Gan, and S. Han. HAT: Hardware-aware transformers for efficient natural language processing. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7675-7688, Online, 2020. Association for Computational Linguistics. doi: 10. 10.18653////0000.ac hww.://2....mmmmi....6..... URL https://aclantholegg otg./200.acclmminn..6.. 686.
acl-main.
[33] H. Wang, W. Wang, and Liu. Temporal Memory Attention for Video Semantic Segmentation. 2021. URL attps://arzivv
ArXiv preprint,
[34] Z. Wu, Z. Liu, J. Lin, Y. Lin, and S. Han. Lite transformer with long-short range attention. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenReview.net, 2020. URI. https://openreviier net/forum? id= BуеMP1HKPH.
[35] K. Xu, C. Li, Y. Tian, Sonobe, K. Kawarabayashi, and Jegelka. Representation learning on graphs with jumping knowledge networks. In J. G. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018 Stockholmsmäs- san, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning
13

---

Research, pages 5449-5458. PMLR, 2018. URL http:///rrooeedings.uu mlr.......rrr....mm.. /tt. xu18c. html.
[36] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, How powerful are graph neural networks? In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL pstpss//openreviee net/forummie ryGs61A5Km.
[37] Z. Ying. J. You, C. Morris, X. Ren, W. L. Hamilton, and J. Leskovec. Hierarchi- cal graph representation learning with differentiable pooling. In S. Bengio, H. M. Wal- lach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31: Anmual Conference on Nearal Informa- tion Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, http://rrroecdinn.rrrrrrpppppppp neurips httpp/pppp///////////////// pages 4805-4815, 2018. URL Att.rractccstttttt.t..oo... .tmll.
[38] Zhang, H. Zhang, C. Xia, and Sun, Graph-Bert: Only Attention is Needed for Learning Graph Representations. ArXiv preprint, 10020000051400 2020. URL htttts://arxiv org/ abs/2001. 0/11/2000..111..... 05140.
[39] M. Zhang. Z. Cui, M. Neumann, and Y. Chen. An end-to-end deep learning architecture for graph classification. In S. A. Mcllraith and K. Q. Weinberger, editors, Proceedings of the Thirty-Secone AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposhum Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 4438 4445. AAAI Press, 2018. URL httpps//wwat aaai org/ erg//cs////eoooooooooooooeoooeco /index..... php/AAAT/AAA AAAT/AAAII8/ www.///////ppppriiee///ee///
[40] J. Zhu, Y. Yan, L. Zhao, M. Heimann. L. Akoglu, and D. Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, De- cember 12, 2020, virtual, 2020. URL https: pttp//////...//t/////r//ooooooa pwtpp/oinoee....c/ee/ wwwpiinnnnn..uun..eeeeeee wttpiiss.cppppppee cwtppper/ppppccccccptcccceee.aea /0aper/2020// /020 hht.//88a22arrrrr000860888424223 Abstrtatt..........ooaa...aaaa.. html.
14


Reviews:
[{"review_id": "SjFuOJsw1I", "reviewer": "Reviewer_ooyr", "summary": "The paper proposes that adding transformers on top of Graph Neural Networks layers aids performance, and furthermore that adding a readout position is a better way to get a final output vs. simple aggregation strategies.  Other papers have in various forms attempted to add transformers to neural networks, but this paper uses a position-encoding free, approach that performs better while being simpler.  This also demonstrates the importance of long range information propagation in solving GNN problems.  They demonstrate the superior performance of their method empirically in a variety of interesting benchmarks.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: Other papers have applied Transformers on top of GNNs but this paper demonstrates that a simpler approach which completely ignores position encoding for transformer part actually results in better performance in the tested applications.  It also introduces using the <CLS> readout position, as done in sequence applications, helps performance in the graph neural network application, which is apparently novel in this context as well.\n\nImpact: The authors empirically demonstrate performance improvements on a variety of datasets.  Furthermore, this paper can also lead that to many other potential network architectures that can further improve performance, such as alternating between transformer and GNN layers.  It also shows the importance of long distance information propagation in solving real graph problems.\n\nClarity:  The paper is well written and easy to follow.  Diagrams are of a good quality and results and their exposition are easy to follow.\n\nQuality:  Submission appears technically sound and is supported by empirical , if not theoretical, evidence.  Ablation studies were performed to narrow down the contributions by the various contributions suggested by the paper, showing the importance of each stage.  \n\nAs a comment however, the paper doesn't demonstrate that actual position encoding isn't helpful - instead it shows that the currently tested schemes are not helpful.  There might be other encodings that perform even better than the suggested approach.     \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have address limitations and potential negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "PmEcukoVXj_", "reviewer": "Reviewer_5JC1", "summary": "This paper proposes to combine GNN with a permutation-invariant transformer called GraphTrans for the graph classification tasks. The GNN module is used to learn representations from graph structure,  while the transformer module without a positional encoding is to learn long-range pairwise relationships, with \"CLS\"-like readout to obtain a global graph embedding. Experimental results show that the proposed simple architecture leads to state-of-the-art results on several graph classification tasks, better than other GNN models. These results also suggest that modeling all pairwise node-node interactions in the graph is\nparticularly important for large graph classification tasks.", "questions": "", "limitations": "", "rating": 6, "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": "Pros:\n1. GraphTrans proposes to use transformer layers (without position embeddings) to learn the pairwise node interactions and summarize the graph representation after a normal GNN model. \n2. Adding this kind of transformer to the GNN improves the performance of various graph classification tasks.\n\nCons:\n1. The number of parameters in GraphTrans is much bigger (maybe doubled) than its GNN version without a transformer (I assume all experiments used 4 layers of transformers as stated on page 6). Thus the improvement presented in Table1-3 may not be fair comparisons.\n2. Combining Transformer with GNN is very common for NLP tasks (pre-trained transformer LM as an encoder for input text sequence), followed by GNN on graphs such as knowledge graphs or dependency parsing trees. Thus the novelty of GraphTrans in this paper is rather limited. I do not agree with the statement that the transformer in GraphTrans is learning \"long-range\" relationships, because the module is computing any pair of feature interactions, with attention weights to control the contribution of each node to the final graph embedding. So it would make sense to try another set of experiments: to switch the order of transformer and GNN, i.e use transformer module first and then GNN, and see the results.\n3. Since the transformer uses self-attention, it would make sense to compare to GAT-like GNN models (for example, the recent paper on direct multi-hop attention network, although this paper only showed results on node classification and knowledge graph embedding, not on graph classification.\n4. The limitation of GraphTrans is that it is only for graph-level classification, and is not suited to node classification. \n\nQuestions:\n1. The last row of ablation results in Table 5 is explained in lines 290-292: not sure how the embeddings of input graph are concatenated with input embedding of the transformer, and where they are used.\n\nSome typos on line 110, Figure 2 caption, line 286, line 292 need to be fixed.\n\n***\nAfter reading the authors' responses to my questions, I have adjusted my review score. I am not convinced on the novelty side of the method. However, if only considering the graph classification task, their experimental results have shown the effectiveness of the proposed method.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above comments.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "BXXVSw-jDl", "reviewer": "Reviewer_SioY", "summary": "Current GNN methods fail at utilizing long-range dependencies in graphs due to over smoothing. However, in some cases, long-range information might be useful. Inspired by the success of transformers in computer vision tasks, this paper tackles the challenge of learning long-range dependencies in GNNs by simply augmenting a common GNN architecture with a transformer sub-network. They also borrow a “readout” token from NLP which improves the final learned representation of the graph.", "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": "1. **Scalability - $O(n^2)$ memory complexity**\n\n   My main concern regarding this paper - is its scalability which is very shortly discussed in the checklist. The transformer subnetwork has to compute and hold in memory attention maps of size, which for graphs already reaching ~100 nodes it could raise a memory issue. Unlike NLP tasks where a usual sentence would contain at most tens of words, graph learning tasks could reach graphs of thousands of nodes. \n\n2. **Originality**\n\n   The authors fail to mention that global attention in graph networks has already been introduced in [1]. The difference between [1] and these works is that the global attention layers are augmented to each GNN layer in [1] and not just at the end. Also, [1] deals with the scalability issue by learning a low-rank representation of the attention matrix having a memory complexity of $O(kn)$ where $k$ is the rank and $k<<n$. \n\n   I therefore feel that the differences between the methods are quite minor unless we see empirical evidence or theoretical justification as to why this work is better and novel than [1]. \n\n3. **Experimental Evaluation**\n\n   - The method is only tested on graph classification tasks. Is the transformer subnetwork also beneficial for node classification and link prediction? \n   - Significantly better performance has already been achieved on the NC1 and NC109 datasets in [2]. Is the setting different?\n\n\n   \n\n***Other comments***\n\n- Typo in the title of section 3 \n\n  > Motivation: Learning to model long-range pairwise interactions in gr\n\n  What is gr?\n\n\n\n---\n\n[1] Puny, O., Ben-Hamu, H., & Lipman, Y. (2020). Global Attention Improves Graph Networks Generalization. *arXiv preprint arXiv:2006.07846*.\n\n[2] Morris, Christopher et al. “Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings.” arXiv: Data Structures and Algorithms (2020): n. pag.\n\n\n---\nAfter reading the authors' responses and the other reviews I think the paper still lacks novelty, however it shows strong performance. I therefore update my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors shortly discuss the limitations in the checklist section as mentioned above in the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "0Uiz5o6Jvd2", "reviewer": "Reviewer_XZ8p", "summary": "This work proposes to use a transformer that attends over all nodes in the graph, given an intermediate representation obtained using a standard GNN module. Contributions 1) usage of a self-attention mechanism that takes into account all nodes in the graph, as opposed to previous methods discussed in the related work. 2) the removal of the positioning encoding to allow permutation invariance. 3) Quantitative results on several datasets, overcoming the baselines and supporting the method with empirical evidence. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "The paper is well written and clear. The work is well positioned with respect to existing work, to the best of my knowledge, clearly stating what are the benefits and contributions of the proposed method. \n\nThe usage of a transformer to learn long-range dependencies is well motivated, drawing evidence from the NLP and vision communities. The method is simple and flexible to the GNN backbone used, as shown in the experimental section. \n\nThe technical novelty is moderate, but the method has been tested on several datasets, showing good results and overcoming a basic Transformer and other GNNs. \n\n\nAdditional questions/comments: \n- In equation 3, it seems it should be $ \\alpha^l_{v,w} = softmax(\\alpha^l_{v,u}) $\n- What happens if a positional encoding is used? I would expect the quantitative results to degrade, but it might be a relevant study to show that the choice of no positional encoding is beneficial for the model. \n- What is the computational cost overhead of adding GraphTrans to a specific backbone? And how many more parameters does it introduce?\n\nOverall, it is a relevant contribution to the field that comes from a sound motivation and is sufficiently benchmarked in the experimental section. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are not discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The majority of the reviewers recommend accepting this paper (3 of 4).
The only reviewer not recommending acceptance did not properly engage in discussion and the authors responded to their concerns.
The AC recommends acceptance.

Decision: Accept (Poster)