Relational Attention: Generalizing Transformers for Graph-Structured Tasks
Authors: Cameron Diao
Ricky Loynd
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Graph Neural Networks
Transformers
Graph Representation Learning
Neural Algorithmic Reasoning

Abstract: Transformers flexibly operate over sets of real-valued vectors representing task-specific entities and their attributes, where each vector might encode one word-piece token and its position in a sequence, or some piece of information that carries no position at all. As set processors, transformers are at a disadvantage in reasoning over more general graph-structured data where nodes represent entities and edges represent relations between entities. To address this shortcoming, we generalize transformer attention to consider and update edge vectors in each transformer layer. We evaluate this relational transformer on a diverse array of graph-structured tasks, including the large and challenging CLRS Algorithmic Reasoning Benchmark. There, it dramatically outperforms state-of-the-art graph neural networks expressly designed to reason over graph-structured data. Our analysis demonstrates that these gains are attributable to relational attention's inherent ability to leverage the greater expressivity of graphs over sets.

Published as a conference paper at ICLR 2023
RELATIONAL ATTENTION: GENERALIZING TRANSFORMERS FOR GRAPH-STRUCTURED TASKS
Cameron Diao
Ricky Loynd
Department of Computer Science Rice University
Microsoft Research
ri Filloyddmiicroee wtw.yndddmmcooofot.coooo
cwd28 .dd
ABSTRACT
Transformers flexibly operate sets of real-valued vectors representing task- specific entities and their attributes, where each vector might encode one word- piece token and its position in sequence, carries no position at all. But as set processors, standard transformers are at a disadvantage in reasoning over more general graph-structured data where nodes represent entities and edges represent relations between entities. To address this shortcoming. we generalize transformer attention to consider and update edge vectors in each transformer layer. We evaluate this relational transformer on a diverse array of graph-structured tasks, including the large and challenging CLRS Algorithmic Reasoning Benchmark. There, it dramatically outperforms state-of-the. art graph neural networks expressly designed to reason over graph graph-structured data. Our analysis demonstrates that these gains are attributable to relational attention's s inherent ability to leverage the greater expressivity of graphs over sets.
piece of information that
INTRODUCTION
Graph-structured problems turn up in many domains, includ-
RT (Ours)
67%
ing knowledge bascs (Hu et al. 2021 Bordes et al. 2013). communication networks (Leskovec et al. 2010). citation net-
PGN-m
48%
works (McCallum et al. (000), and molecules (Debnath et al..
PGN-u
46%
1991 Zhang al. 2020b). One example is predicting the
bioactive properties of molecule, where the atoms of the
MPNN
49%
molecule are the nodes of the graph and the bonds the edges. Along with their ubiquity, graph-structured problems vary widely difficulty. For example, certain graph prob- lems can be solved with a simple multi-layer perceptron, while others are quite challenging and require explicit modeling of relational characteristics.
MPNN-pr
45%
GAT-v2
41%
GAT-v1
42%
DeepSets
49%
DeepSets-pr 43%
Graph Neural Networks (GNNs) are designed process graph- structured data, including the graph's 's (possibly directed) edge structure and (in some cases) features associated with the edges. In particular, they learn represent graph features by passing messages between neighboring nodes and edges, and updating the node and (optionally) edge vectors. Importantly, GNNs typically restrict message passing to operate over the edges in the graph.
Figure 1: The relational transformer (RT) outperforms baseline GNNs on set of 30 distinct graph-structured tasks from CLRS-30, averaged by algorithm class.
Standard transformers lack the relational inductive biases (Battaglia et al. 2018) that are explicitly built into the most commonly used GNNs. Instead, the transformer fundamentally consumes un- ordered sets of real-valued vectors, injecting no other assumptions. This allows entities carrying domain-speciff attributes (like position) to encoded vectors for input to the same transformer architecture applied to different domains. Transformers have produced impressive results in wide
Work done during an internship Microsoft Research.

---

Published as a conference paper at ICLR 2023
One layer of computation
Edge Vector Incorporation
Transformer Machinery
None
Some
Full
Round-trip node- edge communication
RT: Relational Transformer
Some GNNs
A few models
Restricted node- edge communication
Most common GNNS
Some GNNs and transformer variants
Some transformer variants
No edge vectors
Standard transformer
Figure 2: Categories of GNNs and Transformers, compared in terms of transformer machinery and edge vector incorporation. Model categories tested in our experiments are marked in bold.
variety of domains, starting with machine translation (Vaswani et al. 2017). then quickly impacting
language modeling (Devlin et al. 2019) and text generation (Brown et al. 2020). They are revolu- tionizing image processing (Dosovitskiy et al., (221)) and are being applied to a growing variety of
settings including reinforcement learning (RL), both online (Loynd et al. 2020 Parisotto et al. 2020)
and offline (Chen et al. 2021 Janner et al. 2021).
Many of the domains transformers succeed in consist of array-structured data, such as text or images. By contrast, graph data is centrally concerned with pairwise relations between entities, represented as edges and edge attributes. Graphs are more general and expressive than sets, in the sense that a set is special case of graph- one without edges. So it is not immediately obvious how graph data can be processed by transformers in way that preserves relational information. Transformers have been successfully applied to graph-structured tasks in one of broad ways. Certain works, most recently TokenGT (Kim et al. 20222. encode graphs as sets of real-valued vectors passed to standard transformer. Other works change the transformer architecture itself to consider relational information, e.g. by introducing relative position vectors to transformer attention. We discuss these and many other such approaches Section
Our novel contribution is relational attention, mathematically elegant extension of transformer attention, which incorporates edge vectors as first-class model components. We call the resulting transformer architecture the Relational Transformer (RT). As a native graph-to-graph model, RT does not rely on special encoding schemes to input or output graph data.
We find that RT outperforms baseline GNNs large and diverse set of difficult graph-structured tasks. In particular, RT establishes dramatically improved state-of-the-ae performance (Figure D over baseline GNNs the challenging CLRS-30 (Veličković et al. (2022), which comprises 30 different algorithmic tasks in a framework for probing the reasoning abilities of sopph-to-gaphh models. To summarize main contributions:
We introduce the relational transformer for application to arbitrary graph-structured tasks, and make the implementation available at /https:// hwt.ggitthb.cooooaaooooo htt.:/Cammoonoii re seelational-rranffooo
We evaluate the reasoning power of RT wide range of challenging graph-structured tasks, achieving new state-of-ther thrth-rr results on CLRS-30.
We enhance the CLRS-30 framework to support evaluation of a broader array of models (Section 5.1.2).
We improve the performance of CLRS-30 baseline models by adding multi-layer functional- ity, and tuning their byperparameters (Section 5.1.I. 3.1.I)
2 GRAPH NEURAL NETWORKS
We introduce the graph-to-graph model formalism used in the rest of this paper, inspired by Battaglia et al. 2018). The input graph is a directed, attributed graph = (N, &), where / an unordered of node vectors n; E Rdd, denoting the i-th node. & is of edge vectors eiy Rd,, where directed edge (i, points from node node i. Each layer in the model accepts graph G1 as
2

---

Published as a conference paper at ICLR 2023
imput, processes the graph's features, then outputs graph G with the same structure as G', but with potentially updated node and edge vectors. Certain tasks may also include a single global vector with the imput output graph, but omit those details from our formalism since they not what distinguishes the approaches described below.
Each layer of graph-to-graph model is comprised of two update functions & and aggregation function
Node vector n² = on n; ①
20th (e
n', mi.
jEC,
Edge vector e de (ely el n 1+1
n 1
where L; denotes the of node i's neighbors (optionally including node i), and thth denotes message function. The baseline GNNs listed below let de be the identity function such that .+1 e ej for all edges (i, Furthermore, they use permutation-invariinn aggregation function for + The following details are from Veličković et al. 2022):
In Deep Sets (Zaheer al. 2017), the only edges self-connections each L is singleton containing node
In Graph Attention Networks (GAT) /Veličković al. 2018 Brody and the message function 1tth merely extracts the sender features; ahtt kj
2022
self-attention, W Wmn.. where
W m a weight matrix.
In Message Passing Neural Networks (MPNN) (Gilmer et al. 2017 edges lie between any pair of nodes and + the max pooling operation.
In Pointer Graph Networks (PGN) (Veličković et al. 2020), edges are constrained by the adjacency matrix and + the max pooling operation.
RELATIONAL TRANSFORMER
We aim to design mathematically elegant extension of transformer attention, which incorporates edge vectors as first-class model components. This goal leads us to the following design criteria:
1. Preserve all of the transformer's original machinery (though still not fully understood), for its empirically established advantages.
2. Introduce directed edge vectors represent relations between entities.
3. Condition transformer attention on the edge vectors.
4. Extend the transformer layer to consume edge vectors and produce updated edge vectors.
5. Preserve the transformer's ' O (N²) computational complexity.
3.1 RELATIONAL ATTENTION
(See Appendix A for a mathematical overview of transformers.) In addition to accepting node vectors representing entity features (as do all transformers), RT also accepts edge vectors representing relation features, which may include edge-presence flags from an adjacency matrix. But RT operates over fully connected graph, unconstrained by any input adjacency matrix.
Transformer attention projects QKV vectors from each node vector. then computes dot-product between each pair of vectors qi and ky. This dot-product determines the degree to which node attends to node Relational attention's 's central innovation (illustrated in Figure 3) is to condition the QKV vectors on the directed edge e;y between the nodes, by concatenating that edge vector with each node vector prior to the linear transformations:
q [n. eiy] W
kij [nj. e.j W
Vij -n-inj eig A
where each weight matrix W is now of size (d) xd,,, and d, the edge vector size. To implement this efficiently and exactly, split each weight matrix W into separate matrices for
3

---

Published as a conference paper at ICLR 2023
Rj
9iki
k Qi
a; softmaxj
a; = softmax,
Vij
ddn
Vdn
Figure 3: (Left) Standard transformer attention conditions the QKV computation on node vectors.
(Right) Relational attention conditions this computation the intervening edge vector well.
projecting node and edge vectors, project the edge vector to three embeddings, then add those to the node's usual attention vectors:
d. W? e W ki (n, W e. W
Viy (n, W + e, W W.
(4)
While we have described relational attention in terms of fully connected self-attention, it applies equally restricted forms of attention such as causal attention, cross-attention, or even restricted GAT-like attention that passes messages only over the edges present in a graph's 's adjacency ma- trix. Relational attention compatible with multi- head attention, and leaves the transformer O (N²) complexity unchanged. Our implementation maintains the high GPU utilization that makes transformers efficient.
3.2 EDGE UPDATES
To update edge vectors in each layer of processing, follow the general pattern used by transformers to update node vectors: first aggregate messages into one, then use the result to perform a local update. In self-attention each node attends to all nodes in the graph. But having each of the N2 edges attend to N nodes would raise computational complexity to O (N*), Instead, we restrict the edge's aggregation function gather messages only from its immediate locale, which consists its two adjoining nodes, itself, and the directed edge running in the opposite direction:
++1 = the (ely- e n ,
(5)
We compute the aggregated message m by first concatenating the four neighbor vectors, then applying a single linear transformation the concatenated vector, followed by ReLU non-linearity:
m ReLU (concat (el e/ n. 1+1 m W.)
(6)
where W4 E (2d, Xdeea, and the non-linear ReLU operation takes the place of the non-linear softmax in regular attention.
The remainder of the edge update function is essentially identical to the transformer node update function:
n'y = LayerNorm (mls Ws + ely))
1+1 ij
LayerNorm (ReL.U(u)) Ws) =,y))
(7)
where W; Rdeiixd, We Rdexden2 W, Rdaaadd and dehi and deni are the hidden layer sizes of the edge feed-forward networks. Node vectors updated before edge vectors within each RT layer, so that a node aggregates information from the entire graph before its adjoining edges use that information in their local updates. This is another instance of the aggregate-thenn-uddate pattern employed by both transformers and GNNs for node vectors.
PRIOR WORK
We categorize, then discuss prior works based on their use of transformer machinery. We further divide each category based edge vector incorporation, highlighting works that use full node-edge round-tripping, here defined as the process in which edge vectors directly condition node updates and node vectors directly condition edge updates. See Figure for visual comparisons.
4

---

Published as a conference paper at ICLR 2023
Encoding Graphs to Sets For clarity, we define the transformer architecture to exclude any modules that encode inputs to the transformer or decode its outputs. Several prior works have made progress on the challenge of applying standard transformers (Vaswami et al. 2017) to graph-structured tasks by representing graphs as sets of tokens, e.g. with positional encodings. TokenGT (Kim et al. 2022), for example, treats all nodes and edges of graph independent tokens, augmented with token-wiss, embeddings. Graphormer (Ying et al.] 2021) and Graph-BERS (Zhang et al., (020a) introduce structural encodings that are applied to each node prior transformer processing. GraphTrans (Wul et al., (021) and ReFormer (Yang et al. 2022 perform initial convolutions or message passing before the transformer module.
Relative Position Vectors A number of prior works have modified self-attention to implement relative positional encodings (Ying et al. 2021| Cai & Lam 2020b Shaw et al.) 2018 Hellendoorn et al.. 2020; Dai et al. 2019). To compare these formulations with RT, we expand relational attention s dot-product into four terms as follows:
q:yk, =
(In,,
(8)
= (n W + tej W (n, T te, +e, W
(9)
(n. + e; w (k) + (eiz (e)) )
(10)
= W2 (n. W + n. (ej w + e (
+ te, (e,, (
(11)
The transformer of Vaswani et al. (017)) employs only the first term. The transformer of Shaw et al. (2018) adds part of the second term, leaving out one weight matrix W.K and GREAT (Hellendoorn
ct [lal]][000 2020) adds the entire third term. The Transformer-XL. (Dai et al. 2019) and Graph Transformer of Cai & Lam (2020b) use parts of all four terms, but leave out two of the eight weight matrices W and W Each work above uses edge vectors only for relative positional information. RT employs all four terms, allows the edge vectors to represent arbitrary information depending on the task, and updates the edge vectors in each layer of computation.
Transformers With Restricted Node-Edge Communication A few prior graph-to souph-to-graph transform- ers restrict round-trip communication between nodes and edges. EGT (Hussain et al.] (022) does a form of node-edge round-tripping but introduces -callr bottlenecks (per-edge, per-head). The Graph Transformer Dwivedi & Bresson (2021), SAT (Chen et al.] 2022). and SAN (Kreuzer et al., 202 condition node attention coefficients on edge vectors, but they do not explicitly condition node vector updates on edge vectors. GRPE (Cai & Lam| 2020a) also conditions node attention on edge vectors, e.g. by adding edge vectors to the node value vectors. But the edge vectors themselves are not explicitly updated using node vectors.
Highly Modified Transtormers Bergen al. (202I) introduce the Edge Transformer which replaces standard transformer attention with a triangular aaa attention mechanism that takes edge vectors into account and updates the edge vectors in each layer. This differs from RT in three important respects. Finst, triangular attention is completely novel form of attention, unlike relational attention which is framed as a natural extension of standard transformer attention. Second, triangular attention ignores node vectors altogether, and thereby requires node input features and node output predictions to be somehow mapped onto edges. And third, triangular attention's 's computational complexity is O (N*) in the number of nodes, unlike RT's relational attention which maintains the O (N2) transformer complexity. Like Edge Transformer, Nodeformer (Wu al., 2022) employs novel form of attention, but in this case with O (N) complexity. Nodeformer does not perform node-edge round -oiipiipi and introduces single-scale scalar bottlenecks per-edge. Another transformer, GraphGPS (Rampasek) et al. 2022), is described by the authors as an M Transformer hybrid, which does support full node-edge round-tripping. Unlike RT, GraphGPS represents a significant departure from the standard transformer architecture.
Finally, attentional GNNs, such as GAT (Veličković et al., 2018), GATv2 (Brody et al. 2022). Edgeformer (Jin et al. (003), kg Traansforrer (Liu et al. 2022). Relational Graph Transformer (Feng et al. 2022). HGT (Hu et al. 2020), and Simple-HGr HGN (Ly et al. 2021) aggregate features across transformer-style attention coefficients. However, unlike transformers, attentional GNNs only compute attention over input edge vectors, and (except in Edgeformer and kg (gTrrssformer) the edge vectors not updated in each layer. In particular, kg Transfforrrr, Relational
neighborhoods based
5

---

Published as a conference paper at ICLR 2023
Graph Transformer, HGT, and Simple-HGN modify transformer attention to consider hetereogeneous structures in the graph data, such that the model can differentiate between types of nodes and edges.
Other GNNs MPNN (Gilmer et al., 2017) is popular GNN that accepts entire edge vectors input, as do some other works such as MXMNet (hhag et al. 2020ch and G-MPNN Yadati 2020). But
apart from EGNN (Gong & Cheng 2019) and Censnet (Jiang al., 2019), relatively few GNNs update the edge vectors themselves. None of these GNNs use the full transformer machinery, and in general many GNNs are designed for specific settings, such as quantum chemistry.
Unlike any of these prior works, RT preserves all of the original transformer machinery, while adding full bidirectional conditioning of node and edge vector updates.
EXPERIMENTS
We evaluate RT against common GNNs on the diverse set of graph-structured tasks provided by CLRS-30 (Veličković et al. 2022), which was designed to measure the reasoning abilities of neural networks. This is a common motivation for tasking neural networks to execute algorithms (Zarembal
& Sutskever [0144] Kaiser& & Sutskever 2015 Trask et al., 2018 Kool et al.) 2019). RT outperforms baseline GNNs by wide margins, especially tasks that require processing node relations (Section
5.1.5). We further evaluate RT against GNNs on the end-to-end shortest paths task provided by Tang et al. (2020), where again RT outperforms the baselines (Section (5.2). Our final experiment (Appendix B) evaluates RT against a standard transformer on reinforcement learning task where no graph structure is provided. We find that RT decreases error rates of the RI. agent significantly.
5.1 STEP-BY-STEP REASONING
In CLRS-30, each step in task is framed graph-to-gras problem, even for algorithms that may seem unrelated to graphs. To give an example, for list sorting algorithms, each input list element is treated as a separate node and predecessor links are added order the elements. Task data is organized into task inputs, task outputs, and 'hints', which are intermediate inputs and outputs for the intervening steps of an algorithm. Data comprised of combinations of node, edge, and/or global features, which can be of five possible types: scalars, categoricals, masks, binary masks, or pointers.
CLRS-30 employs an encode-process decode framework for model evaluation. Input features are encoded using linear layers, then passed to the model (called a processor) being tested. The model performs one step of computation on the inputs, then it outputs set of node vectors, which are passed back to the model as input on the next step. On each step, the model's 's output node vectors are decoded by the framework (using linear layers) and compared with the targets (either hints or final outputs) to compute training losses or evaluation scores.
Certain CLRS-30 tasks provide global vector with each input graph. As per CLRS-30 specifications, the baseline GNNs handle global vectors by including them as messages in each update step. They do not propagate global vectors through the steps of the algorithm. RT can use two different methods for handling global vectors and evaluate both in Section 5.1.4.
5.1.1 BASELINE GNNS
We began by reproducing the published results of key bascline models on the eight representative tasks (one per algorithm class) listed in Figure of Veličkové et al. (2022) and in our [ For several of the following experiments, we refer to these as the 8 core tasks. Our results on these tasks agree closely with the published CLRS-30 results (Table [T]. See Appendix [ for details of our train/test protocol. We chose not to include Memnet in experiments given our focus on standard GNNs, and given Memnet's poor performance in the original CLRS-30 experiments. Missing detail made it impossible to reproduce the published GAT results CLRS-30.
The published CLRS-30 results show sharp drops in -ittt--distriuttion (OOD) performance for all models. For instance, MPNN's 's average evaluation score drops from 96.63% on the validation set to 51.02% on the test set. We note that small training datasets can induce overfitting even in models that otherwise capable of generalizing to OOD test sets. To mitigate this spurious form of overfitting,
See the final comment in http://gttta..oomomepmmm//rrrsss

---

Published as a conference paper at ICLR 2023
Table I: Mean test scores of all tuned models on the eight CLRS-30 algorithm classes.
Class
Deep Sets
GAT-vI
GAT-v2
MPNN
PGN-u
PGN-m
PGN-c
RT (Ours)
Divide & Conquer
12.29%
15.19%
14.80%
16.14%
16.71%
51.30%
51.30%
66.52% %
Dynamic Programming
68.29%
63.88%
59.22%
68.81%
68.56%
71.07%
71.13%
83.20%
Geometry
65.47%
68.94%
67.80%
83.03%
67.77%
66.63%
67.78%
84,55
Graphs
42.09%
52.79%
55.53%
63.30%
59.16%
64.36%
64.59%
65.33%
Greedy
77.83%
75.75%
75.03%
89.40%
75.30%
76.72%
76.72%
85.32%
Scarch
50.99%
35.37%
38.04%
43.94%
50.98%
54.21%
60.39%
65.31%
Sorting
68.89%
21.25%
17.82%
27.12%
28.93%
2.48%
28.93%
50.01 %
Strings
2.92%
1.36%
1.57%
2.09%
1.61%
1.17%
1.82%
32.52%
Average
48. 60%
41.82%
41.23%
49.23%
46.13%
48.49%
52.83%
66.60%
expanded the training datasets by 10x to 10,000 examples generated from the same canonical random seed of 1, and evaluated the effects on the 8 core tasks. As shown in Table expanding the training significantly boosts the performance of all baseline models. For all of the other experiments in this work, we use the larger training sets of 10,000 examples.
Following Veličković al. 2022), compute results for two separate PGN models, masked (PGN- m) and unmasked (PGN-u), then select the best result on each task to compute the average shown for the combination PGN-c model (which called PGN in the CLRS-30 results). Note therefore that PGN-c does not represent a single model. But it does represent the performance that would be achievable by PGN model that adaptively learned when to use masking.
We found in early experiments that RT obtained far better results than those of the CLRS-30 baseline GNNs. So further enhance the performance of the baseline GNNs, we extended them to support multiple layers (rounds of message passing) per algorithmic step, and thoroughly tuned their hyperparameters (see Appendix C.. This significantly improved the baseline results (see Table I0).
See Table 12 for results comparing CLRS-30 baseline model performances with and without our proposed changes. On certain tasks, baseline score variance increased along with mean scores. For example, the Jarvis' March task, tuning raised the score of MPNN from 22.99 + 3.87% to 59.31 29.3%. See Appendix G for detailed analysis of score variance.
5.1.2 ENHANCEMENTS OF CLRS-30'S FRAMEWORK
Most GNNs consume and produce node vectors, and many also consume edge vectors edge types. However, relatively few GNNs (and none of the CLRS-30 baseline models) are designed to output edge vectors. Because of this, the CLRS-33 framework does not support edge vector outputs from processor network. To test models such as RT that have these abilities, we extended the CLRS-30 framework accept edge and global vectors from the processor each step, and pass these vectors back to the processor as input on the next step. The framework handles node vectors as usual.
In framing algorithms as graph-to-graph tasks, CLRS-30 relies heavily on what it terms node pointer, which is conceptually equivalent to a directed edge pointing from one node to another. Since the CLRS-30 baseline models do not output edge vectors, a decoder in the CLRS-30 framework uses the model's 's output node vectors to create node pointers. But for models like RT that output edge vectors, it is more natural decode node pointers from those edge vectors alone. To better support such models, we added flag to enable this modified behavior in the CLRSS-3 framework.
5.1.3 MAIN RESULTS
After tuning hyperparameters for all models (Appendix Ch. we evaluated RT against the six baseline GNNs on all CLRS-30 tasks, using 20 seeds. The full results are presented in Table 19 RT outperforms the top-scoring baseline model (MPNN) by 11% overall. As bolded in the table, RT 11 out of 30 tasks. RT is also the best-perforiing model on 6 of 8 algorithmic classes (Table D and scores the highest when results are averaged over those classes (Figure I]. See Table for the algorithm-clas mappings. For convenience, Figure I includes the prior results (labeled as MPNN-pi pr and DeepSets-pi for single-layer GNNs from Veličković et al. (2022). In summary, RT significantly outperforms all baseline GNN models over the CLRS-30 tasks.
scores the highest
7

---

Published as a conference paper at ICLR 2023
5.1.4 ABLATIONS
Using only the 8 core tasks (except where noted), we perform several ablations to analyze the factors behind RT's solid performance on CLRS-30.
Transformer We compare RT to standard, set-based transformer (Vaswani et al. 2017) by disabling edge vectors and features in RT. Table [3] shows that performance collapses by almost 40% without edge vectors and relational attention, even after re-tuning its hyperparameters.
Layers The tuned RT uses three layers of computation per algorithmic step. When restricted to a single layer, performance drops drastically (Table 14p, even after re-tuning the other hyperparameters. However, single-layer RT still outperforms the top-scoring MPNN by 10.69 % on the core tasks, suggesting that relational attention improves expressivity even when restricted to single layer of computation.
Global vector Many CLRS-30 tasks provide global feature vector as input to the processor model. We designed RT to handle this global vector by either concatenating it to each input node vector, or by passing it to dedicated core node (Loynd al. 2020; Guo et al. 2019). Hyperparameter tuning chose concatenation instead of the core node option, so concatenation was used in all experiments. But in this ablation, the core-node method obtained slightly higher test scores 7 tasks that use global vectors as inputs to the processor (Table T6). The score difference of 0.08% was marginal, providing no empirical basis to prefer one method of handling the global vector over the other.
Node pointer decoding- We assess impact of the flag we added to the CLRS-30 framework, which can be used to decode node pointers from edge vectors only. Compared to using the original decoding procedure, using the flag improved performance by a small amount (0.30%) (Table [5].
Disabling edge updates We disable edge updates in RT such that RT relies solely on relational attention to process input features. Table 17 shows the resulting drop in performance, from 81.30 % to 53.99 %. This indicates that edge updates are crucial for RT's learning of relational characteristics in the graph data. As final note, RT without edge updates still outperforms the transformer by 11.65 %, demonstrating the effectiveness of relational attention even without updated edges.
5.1.5 ALGORITHMIC ANALYSIS
We investigate the reasoning power RT based on its test performance on specific algorithmic tasks. We only provide possible explanations here, in line with previous work (Veličkovié et al. 2022
Veličković et al. 2020 Xu et al. 2020).
The greedy class is one of two where RT is outperformed (by just one other model). The two greedy tasks, activity selector and task scheduling, require selecting node entities that minimize some metric at each step. For example, in task scheduling, the optimal solution involves repeatedly selecting the task with the smallest processing time. The selection step is aligned with max pooling in GNNs: Veličković et al. (2020) demonstrate how max pooling aligns with making discrete decisions over neighborhoods. Here, each neighborhood represents a set of candidate entities to be selected from. MPNN, PGN-u, and PGN-m all perform pooling at each step of message passing. On the other hand, RT performs soft attention pooling, which does not align with the discrete decision-making required to execute greedy algorithms. This may explain RT's underperformance on activity selector and task scheduling, as well as Prim's 's and Kruskal's.
Underperformance
Overperformance RT overwhelmingly beats baseline GNNs on dynamic programming (DP) tasks. This is surprising. considering that GNNs have been proven to align well with dynamic programming routines (Dudzik & Veličković 2002). To explain RT's overperformance, we consider 1) edge updates and 2) relational attention. For 1), lbarz et al. (2022) observe that several algorithms in CLRS-30 especially those categorized as DP, require edge-based reasoning-
edges store values, and update those values based on other edges' values. These algorithms do not use node representations in their update functions, yet the baseline GNNs can only learn these update functions using message passing between node representations. On the other hand, RT directly supports edge-based reasoning by representing and updating edges. The hypothesis that RT actually uses this ability is supported by the fact that RT beats baseline GNNs most of the 6 edge-centric tasks (Find Maximum Subarray, Insertion Sort, Matrix Chain Order, and Optimal BST), though not on the other 2 (Dijkstra and Floyd- Warshall, For 2), recall from Section 3.1 that relational attention is extension of standard
8

---

Published as a conference paper at ICLR 2023
transformer attention. Standard attention itself is specific instance of the message- function described in Dudzik & Veličkovid (2022), which is part of the author's framework for aligning GNNs and DP routines. To see how this is the case, the reader compare equation equation 12 with equation in Dudzik & Veličkovid (022). From this comparison, and from 1), we expect RT to perform well on both of the edge-centric DP tasks Matrix Chain Order and Optimal BST. We find that RT obtains best scores on both of them, by 5.24% and 3.66% respectively.
5.2 END-TO-END ALGORITHMIC REASONING
CLRS-30 evaluates reasoning ability by examining how closely a model can emulate each step of an algorithm. But may also evaluate reasoning ability by training model to execute algorithm end-to-end (Xu et al. 2020). We use the task provided by [Tang et al. (2020) to evaluate RT in this way. Specifically, task RT with finding shortest path distance between nodes in an undirected lobster graph. The node features are one-hot encoded for source, destination, and remaining. The edge features are binary presence values.
Main Results We use the same experiment settings as Tang et al.) (2020) for the shortest path task. Importantly, we use their method for testing graph size generalizability by training models on graphs of size [4, 34) and evaluating models on graphs of size 100. Fur- thermore, all models use 30 layers. Results are reported using the relative loss metric introduced by the authors, defined as //0l//yl given label y and a prediction ÿ. We compare RT to their two baselines, Graph Convolution Network or GCN (Kipf & Welling 2017) and GAT (Veličković al., 2018). Results are averaged across 20 random seeds. RT outperforms both baselines with an average relative loss of 0.22, compared to GCN's 0.45 and GAT's 0.28 (Figure 4.. These results were obtained without using the iterative module proposed by Tang et al. (2020) that introduces a stopping criterion message passing computations.
RT (ours)
0.22
GAT
0.28
GCN
0.45
Figure 4: Average Relative Loss on Shortest Paths
CONCLUSION AND FUTURE WORK
We propose the relational transformer (RT), an elegant extension of the standard transformer to operate graphs instead of sets. It incorporates edge information through relational attention in principled and computationally efficient way. Our experimental results demonstrate that RT performs consistently well across diverse range of graph- graph-structured tasks. Specifically, RT outperforms baseline GŇNs on CLRS-30 by wide margins, and also outperforms baseline models on end-to-end algorithmic reasoning. RT even boosts transformer performance on the Sokoban task, where graph structure is entirely hidden and must be discovered by the RL agent.
Beyond establishing RT's ffte-of-the-aa results CLRS-30, 30 baseline models, and contribute extensions to the CLRS-30 framework, broadening the scope of models that can be evaluated on the benchmark tasks. All of these improvements make CLRS-30 tasks and baselines more appealing for evaluating current and future models.
enhance performance of the CLRS-
In general, comparing GNNs with transformer-based models like RT on common benchmarks is an important challenge for the community. We have made progress on that challenge by rigorously evaluating RT against standard baseline GNNs on the large and challenging CLRS-30 benchmark, but we leave experiments with other transformer-bast the fact that the CLRS-30 framework written in Jax, and few if any of these transformers have Jax implementations available. But we have improved the CLRS benchmark itself to make such comparisons more practical in the future.
approaches for future work. One difficulty
In future work, we aim to fully leverage the richness of CLRS-30 to more thoroughly investigate RT's capabilities. For example, recent extensions to the CLRS framework (Ibarz et al. (022) allow us to task RT with executing several algorithms simultaneously, which requires knowledge transfer between algorithms. We also plan to evaluate RT on a wider range of woll-wrldd graph settings, such as the molecular domain using the regeescale QM9 dataset (Wu et al. 2018). Finally, aim to relax the locality bottleneck of RT's edge updates by allowing edges to attend to other edges directly in a computationally efficient manner.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We wish thank our many collaborators for their valuable feedback, including Roland Fernandez, who also provided the XT ML tool that made research at this scale possible.
REFERENCES
Peter W. Battaglia, Jessica Hamrick, Victor Bapst, Alvaro
Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals. Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, 2018. URL htttttts::: http://axiv...o abs /b0/ 01261
Leon Bergen, Timothy O' Donnell, and Dzmitry Bahdanau. Systematic generalization with edge transformers. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 1390- 1402. Curran As- sociates, Inc., 2021. URL URL/stttta:///roceeedidie neuriss.eeeppppp. wtteee/.pp..cppappe////////////e
Antoine Bordes, Nicolas Usunier, Alberto Marcia-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Proceedings of the 26th International Conference on Neural Information Processing Systems Volume 2, NIPS' 13, pp. 2787-2795, Red Hook, NY, USA, 2013. Curran Associates Inc.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- tional Conference on Learning Representations, 2022. URL htpp::/ppeezzeveee..
forum? d==22xx mtmm72xxxxxxxc msx 7C1
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Ben- jamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learnrr.. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL ht https:: 74
Deng Cai and Wai Lam. Graph transformer for grap----- learning. Proceedings of the AAAI Conference Artificial h4t.hp/iinnniiiieeeee.332444-6-- Apr. 2020a. doi: 10. 1609/ai/a.i..oo.. v34105.6243
6243
Deng Cai and Wai Lam. Graph transformer for grap-----uuceeeeeeeeeeee learning. Proceedings of the AAAI
Conference on Artificial Intelligence, 34(05)744447471, 2020b. doi: 10. 20.11669/aai.vv4444 v34005. 6243. http:///.oog.aaaaaa.co.//aaaaaaa
aaai
6243
Dexiong Chen, Leslie O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In Proceedings of the 39th International Conference on Machine Learn- ing (ICML), Proceedings of Machine Learning Research, 2022.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. sociates, Inc., 2021, a
Curran As- neurips cc wtc/paper/2021/Fi0
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime G. Carbonell, Quoc Viet Le, and Ruslan Salakhutdinov, Transformer-xi Attentive language models beyond a fixed-length context. In Anna Korhonen, David R. Traum, and Lluís Märquez (eds.), Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume Long Papers, pp. 2978-2988. Association for Computational Linguistics, 2019.
10

---

Published as a conference paper at ICLR 2023
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Corwin Hansch. Structure-activity activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2):786-799) 1991. doi: 10. 100000/m00000aaall URL URL pestps://doi.owtt
1021/ 3m01mmm00100
Jacob Devlin, Ming- Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Shori Papers), pp. 4171-4186 Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 00.18653//1/N11-14233 URL https 7/aclanthor ogy. org/N19-112/2
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL https:tt/ppeeeeeetttss net pet/fooue forum 1d wiadd-iiccFooooo YicbFaNTTy
Andrew Dudzik and Petar Veličković. Graph neural networks are dynamic programmers, 2022. URL 15544
https://arxiv.ct org.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Shanghin Feng. Zhaoxuan Tan, Rui Li, and Minnan Luo. Heterogeneity-aware twitter bot detection with relational graph transformers. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4):3977-3985, Jun. 2022. doi: 10. 10.1609/a w36.://a............. w3w...33.1.2..2.. URLLtttps://ojs.. htt.://ss.aaaaa................. aaai org/ index. Tineexpptt/AAA//atttteeeeeeeeeee
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, pp. 1263-1272. JMLR. 2017.
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 9203-9211, 2019. doi: 10.1 1.110//CVPR.211.000090
Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sebastien Racaniere, Theophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, Greg Wayne, David Silver, and Timothy Lillicrap. An investigation of model-free planning. In ICML, pp. 2464-2473,201
Qipeng Guo, Xipeng Qiu, Pengfei Liu, Yunfan Shao, Xiangyang Xue, and Zheng Zhang. Star- transformer. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers). pp. 1325, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653// 1133,
Vincent J. Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global relational models of source code. In International Conference on Learning Representations, 2020.
URL http::::///penneeeiee net. wtwp://wwww..eett.ttttmme.. Btd.:orrmmdBBllaaaar.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: A large-scale challenge for machine learning on graphs, 2021. URL htttps://axxi...r
abs/ 2tds/2103.094 09430
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In
Proceedings of The Web Conference 2020, WWW '20, pp. 2704-2710, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450370233. doi: 10.1145/3664233338007 URL http::/:/.ooooooooo0001116666663 3380027

---

Published as a conference paper at ICLR 2023
Md Shamim Hussain, Mohammed J. Zaki, and Dharmashankar Subramanian. Global self- as a replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, aug 2022. doi: 10. 10.11457/554678.355226, URL
https:///oi www.idii.oggg/.111 www.ooog.110..... 155221333444555 013233447788339999 3539296
Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Veličković. A generalist neural algorithmic learner. The First Learning on Graphs Conference, 2022. URL https //openreview net/ forum id FebadKZI6Ge
Michael Janner, Qiyang Li, and Sergey Levine. Offline reinforcement learning as one big sequence modeling problem. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 1273- 1286. Curran Associates, Inc., 2021. URL MRR::ttts///p:eeedll http://pproodddd..nner.rrrr....o nwwrine.rrcccmm wttpuriis.ccppppe...repe 2200///ec09946601112330033333333
Paper.pdl
Xiaodong Jiang, Pengsheng Ji, and Sheng Li. Censnet: Convolution with edge-node switching in graph neural networks. In Proceedings of the Twenty-Eighuh International Joint Conference on Artificial Intelligence, LJCAI-19, pp. 1156-2662, International Joint Conferences on Artificial Intelligence Organization, 2019. doi: 00.24963/jeeai2211//366 URL https://do/:oooo
10. N0.24963/ijjem 2Ctc//662
Bowen Jin, Yu Zhang, Yu Meng, and Jiawei Han. Edgeformers: Graph-empowered transformers for representation learning on textual-edge networks. In The Eleventh International Confer- ence on Learning Representations, 2023. URL (ttpttps:: /oppnreveeeeeeeeeeoooeoeeeeoee.e /
net forum?iriii
2RNr
Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms, 2015. URL https://arxiv 22g/abs/1555 08228
Jinwoo Kim, Dat Tien Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL /tpp::ppp///oeeeeeeeeeee net htte:/ooounnniisSAAaaaa
Wouter Kool, Herke Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019. URL jattps:///peerreveee
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL net/ Forum pobrummid--aae 1e=hhhdB-hB---- Tj4yG.
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed networks in social media. Proceed- ings of the SIGCHI Conference on Human Factors in Computing Systems. CHI 10, pp. 1361-1370, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 978 605389299. doi:
10.1145/1753326.11 1753532. (ttthhtts:://d// http///oo.ogg//1///////oo 145/
753326.33. 10l..11111136....... 1753532
Xiao Liu, Shiyu Zhao, Kai Su, Yukuo Cen, Jiezhong Qiu, Mengdi Zhang, Wei Wu, Yuxiao Dong, and Jie Tang. Mask and reason: Pre-training knowledge graph transformers for complex logical queries. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, aug 2022. doi: 10. 010145//353478..5344777 41432F3344678 3539472
Ricky Loynd, Roland Fernandez, Asli Celikyilmaz, Adith Swaminathan, and Matthew Hausknecht. Working memory graphs. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th
12

---

Published as a conference paper at ICLR 2023
International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning mlr
Research, pp. 6404 6414. PMLR. 13-18 Jul 2020. URL
axess/vi19/Lee 1a1.119/oydddaaaaam
Qingsong Lv, Ming Ding, Qiang Liu, Yuxiang Chen, Wenzheng Feng, Siming He, Chang Zhou, Jianguo Jiang. Yuxiao Dong, and Jie Tang. Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks. In Proceedings of the 27th
ACM SIGKDD Conference on Knowledge Discovery & Data Mining. KDD '21, pp. 1150-1160, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 450383322. 10.1 0111444344454434477555
doi: URLpttts::/doi wtt.:/o..rrg....o 1145/34475488 . 67350
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2000.
Emilio Parisotto, Francis Song, Jack Rae, Razvan Pascanu, Caglar Gulcehre, Siddhant Jayakumar, Max Jaderberg, Raphaël Lopez Kaufman, Aidan Clark, Seb Noury, Matthew Botvinick, Nicolas Heess, and Raia Hadsell. Stabilizing transformers for reinforcement learning. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning. volume 1 119 of Proceedings of Machine Learning Research, pp. 7487-7498. PMLR, 13-18 Jul 2020. URL httpt:ttt////ooooe ngs mll www.ppressvllll... h1tp//119paaarr sotto22a html
Ladislav Rampasek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL httpt:::/
woopte//ooommmaooo id LMMaNf 6oxXM
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pp. 464-468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. doi: 10.18653/v N18-2074. URL httpt:/tt:://cccm http::///wcaantthlo..roooro N1 2074
Hao Tang, Zhiao Huang, Jiayuan Gu, Bao-Liing Lu, and Hao Su. Towards scale-invariant graph- related problem solving by iterative homogeneous graph neural networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 978 9781713829546.
Andrew Trask, Felix Hill, Scott E Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arith- metic logic units. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Besa-Bianchi, and R. Garnett (cds.), Advances in Neural Information Processing Systems, volume 31, Curran As- sociates, Inc., 2018, URL htt.::ts:: / http:ttttp///ppoceedege/ neuripss...eursssppepe..p.. cc wwtpccppppppaaa.ee/eee /file/ 2edda1100o0033322226633322233333
Paper. sapeer.pff
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL
Petar Veličković, Adrià Puigdomênech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The CLRS algorithmic reasoning benchmark. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pp. 22084 22102. PMLR, 17-23 Jul 2022. URL htttps:/prroeeddiii wtt.ggg..........s.ee
ml
press/vl 22/vell. wwweiicooiii htmml
Petar Veličković, Lars Buesing, Matthew Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 2232- 2244. Curran Associates, Inc., 2020. URL Intps::tts....t. / neurips....e.....seee..rr. cctpppscccccpcoooccc ccppe/rr//pppap 2020 10t.0//1111166bff 621 F200
13

---

Published as a conference paper at ICLR 2023
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018. ptLlattpps//pppzzeetee wttp://weee.rrrrrrtaaaaooLULLL..
Petar Veličković, Rex Ying. Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations, 2020. URL
net/ fow.ooiddduskoooor -
httts://opperevvll
Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
URL httpp:::/ppseeeeeeetttt.. net forum? watorrumddssMeaaee. ddsMeezXG555
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Sto- ica. Representing long-range context for graph neural networks with global attention. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang and J. Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. 13266- 13279. Curran As- sociates, Inc., 2021. URL http::tttssp/ppccddniniii/ newpeeeeeednnn....r........... neurips CC (a27799116003333453333331211 33d244411144454444-4
pdf
Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chem. Sci., 9:513-530, 2018.
doi: 10. 10.10399/77C0026444 URL http: wwi.dooioooooo..ooo........ orgg/o0g110
1039/C750026647
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2020. URL/Atttss//oppezeee
net htt.:e/etetttoomrmm....eeebeeeee
PS
Naganand Yadati. Neural message passing for multi-relational ordered and recursive hyper- graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 3275-3289. Curran Asso- ciates, Inc., 2020. URL (I/eeddlaaacc522227///daaaeeee
wwwp:iinnnnn.eeririeeeee cc...cc/pe httppssccpppppe//////ee//s// pdf
Xuewen Yang, Yingru Liu, and Xin Wang. Reformer:
The relational transformer for image captioning.
In Proceedings of the 30th ACM International Conference on Multimedia, MM '22, pp. $398-5406. New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 458145039 10.1 01144//503161.3544435
doi:
URL
or0 1ttp://0...1113333111113 /t//////3333111..3888333 3548409
Chengxuan Ying, Tianle Cai. Shengjie Luo. Shuxin Zheng, Guolin Ke. Di He, Yanming Shen, and Tin-Yan Liu. Do transformers really perform badly for graph representation? In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. 28877-28888. Curran As- sociates, Inc., 2021. URL
neurips cc cc/ppaper2021//iL.. Paper... pdf
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poezos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL http:s/ts:// http:///ooooeeeiin..reeoo /nt.o//nn...tttttpp///////eeeeen
cc/
Wojciech Zaremba and Ilya Sutskever. Learning to execute, 2014. URL wtt.ltttsa//xxv..oooo
abs/1410.465 4615
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations, 2020a. URL
Liang Zhang, Xudong Wang, Hongsheng Li, Guangming Zhu, Peiyi Shen, Ping Li, Xiaoyuan Lu, Syed Afaq Ali Shah. and Mohammed Bennamoun. Structure-featte feature based graph adaptive pooling. doi: 29.1445/336622333880333
In Proceedings of The Web Conference 2020. ACM, apr 2020b.
URL https: ww..di.orgg/1. 0tteg/11..144223336663
14

---

Published as a conference paper at ICLR 2023
Shuo Zhang, Yang Liu, and Lei Xie. Molecular mechanics- graph neural network with multiplex graph for molecular structures. In Newr!PS-W W, 2020c.
15

---

Published as a conference paper at ICLR 2023
A TRANSFORMERS
We describe the transformer architecture introduced by Vaswani et al. (2017). This description also applies to most transformer variants proposed over the years. Layer superscripts are employed to distinguish input vectors from output vectors, and are often omitted for vectors inside the same layer.
Although the transformer is set-to-set model, it can be described using our graph-to-graph formalism as limited to computation over nodes only. Each transformer layer is function passing updated node vectors the next layer. single transformer layer can therefore be expressed modified version of equation
1+1 11
tn
n JEC,
(n', m/) 3nth (n/))
(12)
where a mn) computes the attentional coefficient ol applied by node to the value vector v which is computed by th (n'). 1 linear transformation:
a = a (n m')
thth (n')
n
(13)
The attentional coefficients applied by node i the of all nodes j is probability distribution a computed by the softmax function over set of vector dot products:
9:k
a; = softmax,
(14)
dr
The QKV vectors introduced above linear transformations of node vectors:
= n
kj = ny W.
n, W
(15)
where W E Rdd.dd,, W Rd. xd. WV Rd..dd, and d, is the node vector size. These W matrices (like all other trainable parameters Φn) are not shared between transformer layers.
The aggregation function + sums the incoming messages from all nodes L, in the completely connected graph:
mf
a (n/, n²) Th (n/) = Σ Colyy
(16)
jECs
This aggregated message m is then passed to the local update function dn (shared by all nodes), which the following stack of linear layers, skip connections, layer normalization and ReLU activation function:
u' LayerNorm (m: W1 + n!)
(17)
n = LayerNorm (ReLU(u,(,,) W3 + u²)
I+1
(18)
where W1 E Rda.dd, W2 E Rdaxdda, Wg E Rdaaxd. and d.n is the hidden layer size of the ford-forward network.
This overview of the transformer architecture has focused on the fully connected case of self-attention. For brevity we have omitted the details of multi-head attention, bias vectors, and the stacking of vectors into matrices for maximal GPU utilization.
B SOKOBAN EXPERIMENTS
In the experiments described in the main text, the model received edge feature vectors inputs. The question we pose here is whether RT's latent edge vectors can improve reasoning ability even on tasks with graph structure that is hidden, rather than passed to the model in the form of edge vectors. We use the Sokoban (Guez et al.) 2019) reinforcement learning task to investigate. In Sokoban, the agent must push four yellow boxes onto the red targets within 120 time steps. Humans solving these
16

---

Published as a conference paper at ICLR 2023
puzzles tend to plan out which boxes will go onto which targets. Assuming that successful agent will learn a similar strategy, representing each box-to-target pair as directed relation, we hypothesize that RT is more capable than standard transformer at reasoning evaluation, we use RT in place of the standard transformer originally used by the Working Memory Graph (WMG) RL agent (Loynd et al. 2020), then train both modified and unmodified agents the Sokoban task for 10 million time steps.
such pairwise relations. For
Main Results We find that using RT reduces the agent's final error by relative 15%, from 34% to 29% of the puzzles. This improvement is much larger than the confidence intervals (0.3% and 0.7% standard error, respectively). Our results support the hypothesis that RT can learn even hidden graph structure. One alternative explanation would be that the extra trainable parameters added by RT simply improved the expressivity of WMG. But this seems unlikely since hyperparameter tuning of the unmodified WMG agent (Loynd et al. 2020) converged to an intermediate model size, rather than larger model for more expressivity.
C HYPERPARAMETERS
To tune the hyperparameters of RT and the CLRS-30 baseline GNNs, we used Distributed Grid Descent (DGD) (Loynd et al. 2020), self-guided form of random search. Each search was terminated after model performance converged to a stable value. Then 20 additional runs were executed, using the winning hyperparameter configuration, to obtain results free from selection bias. All tuning runs used the CLRS-30 30 protocol described in D except for the following details:
1. To prevent tuning on the canonical datasets or any fixed datasets at all, the dataset generation seeds were randomized at the start of each run.
2. To reduce variance, the minimum evaluation dataset size was raised from 32 to 100.
3. To mitigate the computational costs, all models were tuned on only the 8 core algorithms, and each training run was shortened 32,000 examples.
Very similar procedures were used to tune RT hyperparameters for the other (non-CLRS CLRS-LRS))))) experi- ments. For all experiments, all untuned hyperparameter values were chosen to match the settings of the corresponding baseline models.
C.1 CLRS-30 EXPERIMENTS
Table 2 lists the tuned hyperparameter values for CLRS-30 experiments, and Table reports the sets of values considered in those searches. The runtime sizes of the corresponding models are found in Table along with their training speeds in Table
Table Tuned hyperparameter values for CLRS-30 experiments.
Deep Sets
GAT-v1
GAT=v2
MPNN
PGN-u
PGN-m
RT
batch size num_layers
4
4
4
4
2
2
1
learning rate
2.5c-4
6.3e-4
2.5e-4
1.6e-3
1.6e-3
le-3
2.5e-4
d., de dg
512
512
180
512
nb heads
10
12
12
hiae_size
64
64
16
duh
32
dehl
16
den2
8
ptr from edges
true
graph vec
cat
17

---

Published as a conference paper at ICLR 2023
Table 3: Hyperparameter values considered for CLRS-30 experiments.
batch size
1, 4, 8, 16
num_layers
3,4
learning-rate
4e-5, 6.3e-5, le-4, 1.6e-4, 2.5e.4, 4e-4, 6.3e-4, 1e:3, 1.6e-3, 2.5e.,, 4e-3, 6.3e-3, 1e-2 45, 90, 128, 180, 256, 360, 512
dn = dg
nb_heads
3, 6, 10, 12,
head size
8, 12, 16, 24, 32, 45, 64
dnn
4, 8, 12. 16, 24, 32, 45, 60
deai
12. 16, 24, 32, 45, 64
den2
6, 8, 12, 16, 24,32,44
ptr orrfmommedge
false, true
graph_vee
core, cat
Table 4: Number of trainable parameters in each model tested CLRS-30 30, including the framework's 's encoding and decoding layers, on the reference algorithm Bellman Ford.
Deep Sets
GAT-v1
GAT-v2
MPNN
PGN-u
PGN-m
RT
tuned untuned
8,675,332 414,468
11,168,732 418,960
17,730,076
6,573,060
816.844 414,468
10,777,604 414,468
1,103,404
397,957
414,468
Table Training speed in examples per second on a T4 GPU, on the reference algorithm Bellman Ford.
Deep Sets
GAT-v1
GAT-v2
MPNN
PGN-u
PGN-m
RT
tuned untuned
13.4
14.8
10.1
15.7
18.7
11.6
8.7
128.9
140.7
134.8
128.8
128.6
128.6
C.2 LOBSTER GRAPH HYPERPARAMETERS
Table 6 lists the tuned hyperparameter values for RT on the shortest-path task over lobster graphs, along with the sets of values considered in that search.
C.3 SOKOBAN HYPERPARAMETERS
Table 7 lists the tuned hyperparameter values for RT on the Sokoban task, along with the sets of values considered in that search.
D TRAIN/TEST PROTOCOL
Except where specifically noted, our experiments follow the exact train/test protocol defined by CLRS-30. CLRS-30 provides canonical datasets (training, validation, and test) which can also be generated from specific random seeds: 1, 2, The graphs in the training and validation datasets contain 16 nodes, while the test graphs are of size 64 to evaluate the aut-of-distribution (OOD) generalization of models. Training is performed on a random sequence of 320,000 examples drawn with replacement from the train set, where each example trajectory contains variable number of reasoning steps. During training, the model evaluated on the validation set after every 320 examples. At the end of training, the model with the highest validation score evaluated on the test set. The average test micro-Fl score is reported for all results. The published CLRS-30 results are reported as averages over random run seeds, but use 20 seeds in all of our experiments.
E TEST RESULTS ON CLRS-30
Test performance of all tuned models evaluated on CLRS-30 may be found in Tables 19 (mean test micro-F1 score) and 18 (standard deviation). On certain tasks in which baseline GNN performances
18

---

Published as a conference paper at ICLR 2023
Table 6: Tuned hyperparameter values for RT on the lobster graph experiment.
Tuned values
Values considered
learning_rate
6.3e-5
4e-5, 6,3e-5, le-4, 1.6e-4, 2.5e-4, 4e-4
output.layer_sizz
180
64, 90, 128. 180, 256, 360, 512
nb_heads
3,4, 6, 8, 10
head_size
12, 16, 20, 24, 28, 32
duh de deh1 dena
12
3,4, 8, 12, 16, 24
128
16, 24, 32, 45, 64, 90, 128
32
12, 16, 24, 45, 64, 90
8, 12, 16, 24, 32, 45, 64
dropout_rate
0.0
0.0, 0.01, 0.02, 0.04, 0.08
grad_clip
128.0
16.0, 32.0, 64.0, 128.0, 256.0, 512.0
Table 7: Tuned hyperparameter values for RT on Sokoban.
Tuned values
Values considered
de
128
8, 12, 16, 24, 32, 45, 64, 90, 128, 180, 256, 360, 512, 720, 1024
dekt
64
6, 8, 12, 16, 24, 32, 45, 64, 90, 128, 180, 256, 360, 512
deN2
12
6, 8, 12, 16, 24, 32, 45, 64, 90, 128, 180. 256, 360, 512
improved, we also observed higher variability in results. Following Veličković et al. (2022), we report the best performance between PGN-u and PGN-m on every task in the column titled PGN-c (for PGN-combination) Note therefore that PGN-c does represent single model.
We bold the results of the best-performing single model for each specific task. RT was the best- performing on 11 out of 30 of the tasks. Overall, MPNN was the top-scoring baseline model, winning on 8 tasks. Deep Sets won on 4 tasks. PGN-u won on task, and PGN-m won on 5 tasks. Finally, GAT-v2 won on task.
Table 1 shows test performances of all tuned models across 8 algorithm classes. As mentioned in Section 5.1.3 RT performed best in 6 out of 8 of the classes, and second-best on greedy algorithms and sorting.
Table shows which algorithms belong to which classes, and which task types. Each algorithm may correspond to multiple task types if the hint and final outputs of that algorithm differ.
Table shows test performance of the baseline GNN models trained on datasets of varying size, without hyperparameter tuning. Specifically, compare test scores between the models trained on datasets size 1000, and datasets size 10000. We note that the results in the first row agree closely with those in the CLRS-30 paper (Table
F CLRS-30 BENCHMARK ABLATIONS
We perform our ablation studies the core CLRS-30 tasks. Table 13 compares the performance of the standard transformer to the performance of RT. Table [hoswwws the drop in test performance that resulted from restricting RT to one layer. The original, tuned RT had 3 layers, and is labeled RT-3. Table 15 shows the marginal improvement that resulted from decoding node vectors using only edge vectors. Table 16 shows the effects that handling global input vectors through a core node (vs. concatenation with the input node vectors) has on RT test performance. RT with core node only won on out of tasks, but had the higher average test performance by 0.08%. Finally, Table 17 shows the drop in test performance that resulted from removing edge updates from RT.
G CLRS-30 MODEL VARIANCE
Table 18 shows that RT produces of the largest standard deviations over random runs. To investigate these results, we first examine the Naïve String Matcher task, where RT's variance the largest value in the table (32.3%). 5 displays each model's distribution of run scores, through
19

---

Published as a conference paper at ICLR 2023
histograms. We see that RT's twenty runs this task obtain wide range of scores, including spike in the range from 80% to 100%, while none the baseline model runs surpass score of 20%. This explains RT's high variance this task compared to the other models. In summary, in case like this higher variance a consequence of higher performance.
The same behavior be inferred without the histograms by examining Table 18 and Table T9 which show that RT's high variance on Naïve String Matcher is associated with far higher mean performance the task than the baseline models. The same pattern apparent for RT's next two highest-variance tasks, Topological Sort and Quickselect.
For broader view of variance, Figure 6 displays the model score distributions over all CLRS-30 tasks. We see that RT's distribution is weighted more heavily than the other models in the >80% range, and underweighted in the <20% range. Mcanwhile, all model distributions are spread quite widely over the five range bins. This spread is quantified numerically by the last row of Table 18 where RT's overall standard deviation is shown be one of the smallest.
Figure 5: Histograms describing the variance model results on Naïve String Matcher, across runs
DeepSets
GAT-v1
GAT-v2
MPNN
PGN-u
PGN-m
RT (Ours)
Number of random runs
0-20%
20-40%
40-60%
60-80%
80-100%
Score ranges of histogram bins
Figure 6: Histograms describing the variance in model results across all runs on the 30 CLRS tasks
DeepSets
GAT-v1
GAT-v2
MPNN
PGN-u
PGN-m
RT (Ours)
Number of random runs
0-20%
20-40%
40-60%
60-80%
80- 10-100%
Score ranges of histogram bins
20

---

Published as a conference paper at ICLR 2023
Table 8: Algorithms and their respective classes and task types. Taking hint targets into consideration, there 3 task types in CLRS-30: node (N), edge (E), and graph (G).
Algorithm
G
D&C
DP
Geo
Graph
Greedy
Search
Sort
String
Activity Selector
Articulation Points
Bellman- Ford
BFS
Binary Scarch
Bridges
Bubble Sort
DAG Shortest Paths
DFS
Dijkstra
Find Max. Subarray
Floyd Warshall
Graham Scan
Heapsort
Insertion Sort
Jarvis" March
KMP Matcher
LCS Length
Matrix Chain Order
Minimum
MST-Kruskal
MST-Prim
Naive String Match
Optimal BST
Quickselect
Quicksort
Segments Intersect
SCC
Task Scheduling
Topological
Total
27
14
3
3
12
2
Table 9: Average scores of untuned baseline models trained either the original small datasets, versus trained on the expanded training datasets, for the 8 core tasks.
Training Set Size
Deep Sets
GAT-v1
GAT-v2
MPNN
PGN-u
PGN-m
PGN-c
1000
45.95%
42.24%
42.53%
54.66%
51.07%
56.18%
61.29%
10000
46. 76%
42.97%
45.37%
56.93%
56.77%
58.20%
67.11%
Table 10: Test score improvements from hyperparameter tuning the 8 core tasks. The drop in score for PGN-m was likely the result of tuning hyperparameters (for all models) on shorter training runs than used for evaluation.
Algorithm
Deep Sets
GAT-v1
GAT-v2
MPNNN
PGN-u
PGN-m
PGN-c
No Tuning
46. 66.70%
42.97%
45.37%
56.93%
56.77%
58.20%
67.11%
Tuning
51.55%
50.47%
48.97%
59.75%
59.97%
57.53%
67.86%
Table 11: Reproduction of baseline model results on the 8 core algorithms.
Results
# Seeds
Deep Sets
MPNN
PGN-c
Published (Veličković al. 2022
3
45.50%
53.05% 54.66%
61.15%
Reproduced (Ours)
20
45.95%
61.29%
21

---

Published as a conference paper at ICLR 2023
Table 12: Test score improvements from augmenting the CLRS-30 baseline models.
Results
#
Sceds
Deep Sets
MPNN
PGN-c
CLRS-30 30 Published Results
3
42. 42.72%
44.99%
50.84%
Our Results
48.60%
49.23%
52.82%
Table 13: Standard transformer ablation (with re-tuned hyperparameters) evaluated the 8 core algorithms.
Algorithm
Transformer
RT (Ours)
Activity Selector
68.01% 1
87.72% 2.7
Bellman-Fordi
39.79% + 2.4
94.24% + 1.5
Binary Search
2.84% 1 0.6
81.48% + 6.7
Find Max. Subarray
26.60% + 6.0
66.52% 3.7
Graham Scan
58.84% 6.9
74.15% 7.4
Insertion Sort
60.57% + 15.7
89.43% 9.0
Matrix Chain Order
80.54% 1 6.8
91.89%
1 1.2
Naive String Match
1.51% % 4 1.7
65.01 % 16.11 32.
Average
42.34%
81.30%
Table 14: Single-layer RT ablation (with re-tuned hyperparameters) evaluated the 8 algo- rithms.
Algorithm
RT-1
RT-3 (Ours)
Activity Selector
83.41% 5.8
87.72%
2.7
Bellman-Foo Ford
93.52% + 1.7
94.24% + 1.5
Binary Search
61.61% 15.1
81.48% + 6.7
Find Max. Subarray
65.07% 4.0
66.52% 3.7
Graham Scan
74.80% 7.7
74.15% 7.4
Insertion Sort
77.54% + 10.3
89.43% + 9.0
Matrix Chain Order
91.05% 11661110 1.0
91.89% 1 1.2
Naive String Match
16.50% 1 23.2
65.01 % 32.
Average
70.44%
81.30
Table 15: Ablation of the node pointer decoding procedure evaluated the 8 core algorithms.
Algorithm
RT with original decoding
with edge-only decoding (Ours)
Activity Selector
88.09% = 5,0
87.72% + 2.7
Bellman-Fort
94.95% = 1.1
94.24% t 1.5
Binary Search
80.06% i 6.6
81.48 % + 6.7
Find Max. Subarray
+ 67.44%
66.52% 3.7
Graham Scan
75.71 % + 10.3
74.15% + 7.4
Insertion Sort
71.32% + 11.0
89.43% % 9,0
Matrix Chain Order
92.12% 0.9
91.8% 1.2
Naive String Match
78.43% 22.5
65.01% % 32.
Average
81.00%
81.30%
Table 16: Ablation of RT core node (vs. concatenation of the global vector) evaluated on represen- tative algorithms that global input features or hints.
Algorithm
RT with core node
without core node (Ours)
Binary Search
75.40% + 11.0
81.48% + 6.7
Find Max. Subarray
66.96% 4.5
66.52% + 3.7
Graham Scan
71.83% 10.2
74.15% 1 7.4
Heapsort
30.67% 18.9
32.96% 14,8
KMP Matcher
0.02% 1 0.0
0 1 0.1
AST--Kuskkal
75.59 % 5.8
64.91 % = 11.8
Task Scheduling
83.09 % + 1.8
82.93% + 1.8
Average
57.65%
57.57%
22

---

Published as a conference paper at ICLR 2023
Table 17: Ablation of RT's edge update procedure evaluated the core algorithms
Algorithm
RT without edge updates
with edge updates (Ours)
Activity Selector
82.13% 1 7.0
87.72% 1 2.7
Bellman-Ford
91.03% + 2.3
94.24% = 1.5
Binary Search
60.29% 12.5
81.48% 6.7
Find Max. Subarray
19.09% + 1.6
66.52% = 3.7
Graham Scan
69.19% + 7.7
74.15% + 7.4
Insertion Sort
22.30% + 8.5
89.43% 9.0
Matrix Chain Order
85.68% + 1.5
91.89% + 1.2
Naive String Match
2.22% 0.8
65.01 32.
Average
53.99%
81.30%
Table 18: Standard deviations 20 seeds for all tuned models all algorithms. Each value in the row "Over All Runs" is not an average variances for each algorithm, but rather the variance across all runs.
Algorithm
Deep Sets
GAT-v1
GAT-v2
MPNN
PGN-u
PGN-m
RT (Ours)
Activity Selector
1.7%
1.4%
2.1%
1.3%
2.6%
1.9%
2.7%
Articulation Points
6.0%
8.0%
6.3%
6.1%
3.5%
7.5%
14.6%
Bellman-Ford
2.4%
1.5%
1.6%
0.9%
1.3%
1.5%
BFS
1.0%
0.4%
0.4%
0.2%
0.3%
0.5%
0.7%
Binary Scarch
3.8%
5.8%
7.9%
5.0%
10.4%
3.7%
6.7%
Bridges
4.8%
6.4%
8.0%
17.8%
11.0%
7.8%
11.8%
Bubble Sort
3.1%
2.5%
1.3%
5.0%
1.9%
0.2%
13.0%
DAG Shortest Paths
3.8%
2.3%
2.2%
3.2%
0.9%
1.6%
DFS
1.9%
2.1%
1.7%
2.7%
1.5%
1.5%
10.5%
Dijkstra
3.6%
9.5%
7.1%
4.3%
11.0%
3.4%
5.8%
Find Max. Subarray
1.5%
2.4%
2.1%
2.9%
1.6%
15.0%
3.7%
Floyd- Ward-Warshall
4.2%
6.0%
3.7%
4.7%
4.8%
2.5%
7.6%
Graham Sean
3.3%
6.6%
5.3%
1.4%
5.7%
6.0%
7.4%
Heapsort
8.8%
3.8%
4.1%
7.1%
8.9%
0.4%
14.8%
Insertion Sort
1.5%
14.8%
11.6%
9.1%
11.2%
0.2%
9.0%
Jarvis' March
8.6%
2.6%
3.9%
29.3%
2.5%
5.8%
2.2%
KMP Matcher
1.0%
0.6%
0.6%
1.1%
0.7%
0.4%
0.1%
LCS Length
6.5%
7.2%
4.6%
2.7%
7.8%
3,5%
4.1%
Matrix Chain Order
2.8%
5.4%
5.1%
2.3%
0.9%
1.1%
1.2%
Minimum
5.8%
2.6%
10.4%
3.4%
3,4%
27.3%
2.0%
MST-Kruskal
4.9%
2.9%
4.2%
5.9%
6.1%
4.3%
11.8%
MST-Prim
11.4%
9.2%
10.7%
5.1%
4.6%
7.2%
7.9%
Naïve String Match
0.3%
0.7%
0.5%
1.7%
0.8%
0.7%
32.3%
Optimal BST
6.0%
5.7%
5.1%
3.5%
2.0%
2.0%
2.6%
Quickselect
2.4%
0.5%
0.4%
1.6%
0.9%
1.0%
17.3%
Quicksort
4.3%
1.3%
3.9%
1.9%
0.2%
13.2%
Segments Intersect
0.7%
0.5%
0.7%
2.5%
0.8%
0.8%
2.6%
SCC
5.9%
8.8%
9.9%
5.2%
6.0%
6.9%
15.2%
Task Scheduling
0.5%
0.4%
0.8%
0.9%
0.5%
0.5%
1.8%
Topological Sort
10.3%
12.7%
17.8%
5.8%
6.5%
10.1%
17.5%
Over All Runs
29.3%
32.0%
31.3%
34.6%
33.1%
35.0%
29.6%
23

---

Published as a conference paper at ICLR 2023
Table 19: Average test scores of all tuned models on all algorithms.
Algorithm
Deep Sets
GAT-v1
GAT-v2
MPNN
PGN-u PGN-m
PGN-c
RT (Ours)
Activity Selector
72.22%
68.89%
67.45%
95.45%
67.05%
69.83%
69.83%
87.72%
Articulation Points
38.50%
31.46%
31.96%
46.21%
46.87%
49.73%
49.73%
34.15%
Bellman-Ford
51.00%
93.10%
93.75%
95.42%
95.83%
95.43%
95.83%
94.24%
BFS
98.14%
99.76%
99.49%
99.78%
99.71%
99.27%
99.71%
99.14%
Binary Search
55.77%
17.21%
31.11%
38.00%
61.71%
87.03%
87.03%
81.48%
Bridges
36.20%
22.90%
24.07%
61.29%
44.72%
57.15%
57.15%
37.88%
Bubble Sort
65.03%
9.69%
8.46%
13.14%
7.54%
2.05%
7.54%
38.22%
DAG Shortest Paths
77.98%
86.44%
89.35%
97.33%
96.23%
98.16%
98.16%
96.61%
DFS
7.62%
11.71%
12.08%
13.85%
10.78%
8.88%
39.23%
Dijkstra
44.51%
61.42%
60.10%
92.18%
78.45%
90.02%
90.02%
91.20%
Find Max. Subarray
12.29%
15.19%
14.80%
16.14%
16.71%
51.30%
51.30%
66.52%
Floyd-Warshall
6.24%
30.53%
37.58%
28.81%
27.60%
39.24%
39.24%
31.59%
Graham Scan
64.48%
65.05%
67.07%
95.31
67.89%
64.66%
67.89%
74.15%
Hcapsort
72.39 %
9.90%
7.65%
27.08%
17.88%
1.60%
17.88%
32.96%
Insertion Sort
72.88%
61.00%
50.19%
50.30%
82.42%
3.64%
82.42%
89.43% %
Jarvis' March
46.01% %
55.40%
50.23%
59.31%
49.54%
49.57%
49.57%
94.57 %
KMP Matcher
3.71% %
1.03%
1.32%
2.35%
1.75%
0.44%
1.75%
0.03%
LCS Length
55.85%
48.14%
48.30%
54.42%
53.85%
56.00%
56.00%
83.32% %
Matrix Chain Order
81.65%
81.59%
65.58%
85.53%
86.65%
86.47%
86.65%
91.89%
Minimum
91.69%
86.87%
80.60%
90.73%
89.22%
70.69%
89.22%
95.28% %
MST-Kruskal
69.07%
67.26%
68.60%
70.84%
63.47%
69.35%
69.35%
64.91%
MST-Prim
35.70%
61.83%
68.72%
86.43%
81.59%
83.61%
83.61%
85.77%
Naïve String Match
2.12%
1.70%
1.81%
1.83%
1.46%
1.90%
1.90%
65.01 %
Optimal BST
67.37%
61.91%
63.78%
66.48%
65.19%
70.74%
70.74%
74.40 %
Quickselect
5.51%
2.03%
2.40%
3.07%
2.00%
4.92%
4.92%
19.18%
Quicksort
65.26%
4.41%
5.00%
17.95%
7.90%
2.63%
7.90%
39.42%
Segments Intersect
85.94%
86.36%
86.10%
94.46%
85.89%
85.66%
85.89%
84.94%
SCC
21.13%
23.66%
29.47% %
12.58%
12.97%
17.20%
17.20%
28.59%
Task Scheduling
83.45%
82.61%
82.61%
83.36%
83.54%
83.62%
83.62%
82.93%
Topological Sort
19.02%
43.47%
43.23%
54.93%
51.71%
64.28%
64.28%
80.62 %
Average
50.29%
46.42%
46.70%
55.15%
51.94%
52.17%
56.57%
66.18 %
24


Reviews:
[{"review_id": "z5Cpo6tF9h", "reviewer": "Reviewer_AFXh", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 relational transformers, extending the transformers architecture to general graph-structured data. Specifically, the proposed relational transformers is a graph-to-graph model with feature updates of nodes, edges, and the global graph vector at each layer. Relational transformers achieve remarkable performance on the CLRS benchmark, comprised of algorithmic tasks such as BFS and insertion sort.", "summary_of_the_review": "Overall, this paper provides technical contributions, is a pleasure to read, and has solid experiments. A few concerns remain in my opinion, and I'm looking forward to discussing them with the authors and revisiting my review and/or score. :)", "strength_and_weaknesses": "Strengths:\n+ interesting research problem of applying GNNs to algorithmic tasks\n+ extensive experiments with solid and consistent performance improvements\n\nWeaknesses:\n- a few reservations about the experiments and the claim that relational transformers is \"a competitive general-purpose model for graph-structured tasks\"\n- minor issues such as more related work and better presentation", "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": "mMDnoNefoXz", "reviewer": "Reviewer_H4RY", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 introduces a new variant of transformers for graph-structured tasks, building on both the original transformer architecture and the \"graph networks\" framework of [Battaglia et al. (2021)](https://arxiv.org/abs/1806.01261). Their model, called \"relational transformer\" (RT), includes edge attributes that participate in the attention mechanism and that are updated at each layer similarly to the transformer's MLP block.\n\nThe authors compare their architecture to the standard set of baseline GNN models for the CLRS algorithmic reasoning benchmark task, and also modify the benchmark to make its interface more expressive. The experiments appear to be very thorough, and the authors both increase the size of the training dataset and tune the hyperparameters for baseline models to ensure that the results accurately reflect the ability of the models to generalize to out-of-distribution graph problems. The authors also include several ablations of their model. Overall, the experiments show that their RT model outperforms the GNN baselines on many of the tasks by a large margin (but not all), and that the edge update mechanism has a significant impact.\n\nThe authors also evaluate their model's ability to solve an end-to-end shortest path problem (where step-by-step supervision is not provided) and a Sokoban task (where no graph structure is provided and the model must learn it on its own). On both of these tasks, the authors again find improvements from incorporating their model.", "summary_of_the_review": "*Initial submission:*\nThe architecture proposed here is interesting and well motivated, and the experimental results are thorough and demonstrate that the model works well relative to ordinary GNNs, which are both reasons for acceptance. My main reservation (and why I gave it a 6 instead of an 8) is that the paper does not currently engage much with prior work on transformer-based graph models (such as TokenGT and Graphormer) in either the introduction or the experiments section.\n\nI think that the authors should acknowledge (in the introduction) what existing transformer graph models have already accomplished and discuss more clearly what their proposal provides beyond these models, instead of framing their ideas as if they are making the first attempt to test a totally new conjecture. The paper would also be stronger if it included empirical comparisons to some of these previous transformer graph models (or at least explained why those models aren't appropriate for the setting considered).\n\n*Revision (as of Nov 12, 2022):*\nThe authors have substantially revised the introduction to better contextualize their contributions relative to prior work, and removed unsupported claims about how their model compares empirically with these other graph-transformer hybrids. I have thus raised my score to 8.", "strength_and_weaknesses": "Strengths\n- The paper is well written and easy to follow.\n- The proposed architecture is quite straightforward and generic, seeming to combine the most important parts of a standard transformer and of the \"graph networks\" framework without adding complex heuristic adjustments.\n- The experiments are very thorough, and the authors describe a number of adjustments they made to improve the performance of the baselines, which makes the strong performance of their proposed model more impressive.\n\nWeakesses\n- **(addressed by new revision)** The framing of the paper in the abstract and introduction does not do enough to contextualize this work relative to the extensive previous work on incorporating relational attention into transformers, in my opinion.\n    - The authors claim that transformers are at a disadvantage for graphs, that they have \"not had the same success\" as GNNs in graph-structured domains, that there is \"no generally applicable way of passing edge feature vectors into a transformer without losing the graph's connectivity information\", and that their work addresses these shortcomings. However, there have been a number of recent works that demonstrate that transformers succeed in graph structured domains, and multiple proposals for passing edge feature vectors into transformers. (The authors discuss some of this in the related work section, which is good. But I think the claims in the introduction should be substantially reduced based on the prior work in this area.)\n- **(mostly addressed by new revision)** Although the authors discuss differences between their model and previous proposals for adding relational attention to transformers (calling most of them \"partially relational\"), they do not include any experiments comparing against these models. It's not obvious to me that the distinction between partially relational and fully relational models is meaningful, or that their approach would work better.\n    - Adding additional experiments comparing against some subset of partially-relational transformers would strengthen the paper. But I would also be satisfied if the authors add to the paper a justification for not including these experiments. (For instance, perhaps the authors only want to claim that transformer variants can work better than GNNs on CLRS and don't want to claim that their model is superior to the \"partially relational\" versions? Or perhaps there is some reason why previous works are not well suited for this task?)\n    - I'd be particularly interested in seeing how the RT models proposed here fare against the recently-proposed TokenGT architecture, since that architecture is a different way of generalizing transformers to operate over graphs in a general-purpose way.\n    - *The revised version of this paper makes it clear that the authors do not intend to claim that their model outperforms other graph-transformer variants in general, and that the code for other graph-transformer models can't be directly applied to the CLRS benchmark used here, which requires JAX code. I still think it would be very interesting to see how this model compares to other approaches like TokenGT, and that those results would improve the paper, but I don't think they are necessary to include.*", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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": "avqfxfGA85g", "reviewer": "Reviewer_eKg9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors introduce the relational transformer, a modification of the conventional transformer architecture to work on graphs. This is not the first instance of transformer-inspired architectures which handle graph input, however a fundamental difference is that this method allows for full edge usage, not only incorporating edge attributes when updating node representations, but also allowing edge representations to be updated as well. Each layer essentially takes an attributed graph to another attributed graph, using local information about nodes (i.e. their neighbors and the edge attributes for edges which connect them) to compute a new representation for the node, as well as using local information (i.e. the edge attribute itself, the nodes it connects to, and the reverse edge attribute) to compute a new edge representation. The restriction to local information when computing new edge representations allows the relational transformer to preserve the $\\mathcal O(N^2)$ computational complexity of the conventional transformer architecture.\n\nThe authors evaluate the new method on the CLRS algorithmic reasoning benchmark. This included the contribution of an extension to this benchmark to allow for models such as relational transformer which update edge representations in each layer, as well as a rigorous strengthening of the baselines by expanding the training datasets and tuning their hyperparameters. The relational transformer is found to outperform these baselines in 12 out of 30, leading to top performance in 6 out of 8 algorithmic classes and scoring highest on average.", "summary_of_the_review": "While this model proposed by this work performs well empirically, I have some concerns with the high variability of these results (as mentioned in the weaknesses section). I also feel the paper is somewhat incomplete in a few areas at this time, and I think it would benefit from a second revision. As such, I do not feel the paper is ready for publication at this time, but am willing to reconsider my recommendation based on the author's response and discussion with other reviewers.", "strength_and_weaknesses": "### Strengths\n1. The idea was pleasingly simple and straightforward, both in motivation and from a technical perspective. The paper is well-structured \n- the authors start by listing a loose set of desiderata for any model which adapts the transformers to graphs (including, in particular, updated edge representations while preserving reasonable computational complexity), highlight the ways in which current approaches do not satisfy these objectives, and then present their method which clearly satisfies the requirements.\n2. The baselines from the experiments are very rigorous, in the sense that the authors took the time to not only reimplement baselines and verify they obtain similar performance to previously reported results, but then further went on to tune the hyperparameters of these baselines, obtaining better results than previously reported.\n\n### Weaknesses / Questions\n1. The standard deviation for RT seems to be much higher than for the other methods, enough so to potentially make the significance of the results and the practical use of RT somewhat questionable. Can the authors provide any insight into why there is more variation with RT than with other methods? In addition, the standard deviation of the baselines also seem to be higher across the board than those reported in the Veličković et al. 2022. Presumably this may be due to the fact that Veličković et al. 2022 only had three evaluations for each, if so then it might be helpful to future readers to explain this difference in the appendix, near where the standard deviations are presented.\n2. While much attention (pun intended) was given to the edge vectors, it seems like the global vectors were mostly an afterthought. In particular, the ablation for global vectors compares two methods - concatenation to each input node vector or passing it to a dedicated core node - and finds that the dedicated core node is slightly better (whereas hyperparameter tuning on previous experiments suggested concatenation was better). The authors note that the difference in score between the two was not statistically significant, and suggest that both methods are effective at handling global features, however to make such a claim it would be useful to have an experiment where the global features are not included. Furthermore, while the average score was very similar, the difference per-algorithm seems quite significant. Given the earlier statement about high variability of results, I also think it would be necessary to consider the variance across multiple runs.\n3. A further question regarding the global vector - in the concatenation method, does the global vector get updated at each layer? (Obviously the core node approach would update every layer as a result of the node updates.) If not, it seems to run somewhat counter to my understanding of the high-level \"pitch\" for this paper, i.e. that learning a fully updated attribute graph at every layer was beneficial. I could imagine there are cases where it is useful for the edges *and* nodes to \"communicate\" shared global information by updating this global representation. While this is indirectly possible with the core node approach, the edges must communicate via updated node representations, which then get passed along additional edges to the core node. The core node (to my understanding of it) is also far from the a \"clean\" way to handle this, as $2N$ new edges must be added as well along which nodes can communicate with the global vector. A proposal for an approach which handles the global vector in a principled way would make the proposed model and paper more complete.\n4. Despite the improved results from properly tuning the baselines, I have concerns that some of the experiments have extremely low numbers, which are the result of an unfortunate choice of hyperparameters. For example, in Table 13 we see that RT-1 performs worse than RT-3, but the results are at least in the same ballpark for most algorithms, whereas for Naive String Match the discrepancy is massive, with RT-1 getting 1.77% whereas RT-3 gets 65.01%. I have similar concerns for the poor performance of the transformer on a few tasks in Table 12.\n5. I do not see GAT nor Memnet in Table 11 (baseline reproduction), both of which were in Veličković et al. 2022. I assume the reason Memnet was not included is because it performed worst in Veličković et al. 2022. If this is the case, I think it would be useful to mention it. As for GAT, it seems that sometimes the original model outperformed both GAT-v1 and GAT-v2. This does not change the principal conclusion of the paper, since it does not outperform RT, but I wonder if the authors have any thoughts as to why this is the case. (It should probably be commented on near the reproduction table, at any rate.)\n6. The commentary in algorithmic analysis is somewhat weak. The authors attempt to draw some conclusions based on intuition of the model's capabilities and the tasks which it significantly underperforms or overperforms, however the conclusions are simply hypotheses at this point, and would require further analysis and/or experiments to back them up. For example, at the end of this section the authors state \"RT can explicitly materialize the DP solution table as its edge vector matrix, and perform updates on each entry using edge updates.\" which may be true, but does it actually do so?\n\n### Suggestions / Typos\n1. The graph-to-graph model formalism described in (1), (2), and (3) does not capture the resulting RT model. Specifically, the edge vector update (2) cannot express the resulting edge vector update (6). If the graph-to-graph model formalism was only intended to abstractly capture the baseline models in section 2, thereby highlighting the distinction of RT, I understand this choice. If not, I just wanted to bring this to your attention.\n2. The comprehensive review of the transformer in the appendix is appreciated, however for those equations which are referenced in the main paper it might be worth considering including them in the main text, so that readers will not have to refer to the appendix simply to follow the main discussion. (These include equation 17, 18, and 21.)\n3. For notational consistency, it might be nice to replace \"nodes\" with \"vertices\", and use $\\mathbf v_i$ for the vertex vectors. (Alternatively, one could replace $\\mathcal V$ with $\\mathcal N$, and all the $v$ subscripts to $n$, to match \"nodes\", but then the notation for neighbors would need to be changed.) Already, at some points $d_v$ is written as $d_n$ (for example, just under equation (4)).\n4. There are a number of places where dimensionality seems incorrect. For example, just under equation (7), I believe it should be $\\mathbf W_4 \\in \\mathbb R^{(2d_e+2d_v) \\times d_{eh1}$.\n5. In $\\mathbf k_{ij}$ and $\\mathbf v_{ij}$, the subscript on $\\mathbf n$ should be $j$, not $i$.\n6. This is very minor, but you can save yourself one line of the equations in section 4 by not distributing the transpose through the matrix-vector products in (11), thereby going directly to (13) and skipping (12).\n2. Page 7: missing reference to figure.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KPDh76f9EF7", "reviewer": "Reviewer_WhvK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose an adaption of transformer attention to graph input. Normally, a transformer takes an unordered set as input, which can not adequately represent the structured nature of a graph. The key change they propose is the inclusion of the directed edge between nodes into the attention mechanism. \nThe authors show the effectiveness of their proposed architecture through extensive experiments on the CLRS benchmark. Across most tasks, the proposed relational Transformer achieves competitive or better performance than the SOTA approaches.\nAn ablation study proves that the performance improvements are caused by the proposed changes in the attention mechanism.\n", "summary_of_the_review": "In summary, the positive points mentioned (clarity of presentation, well-motivated and performant approach, detailed experimental section) clearly outweigh the minor formatting issues. Overall, the proposed approach is a useful and insightful contribution to the field.\nThis leads to my recommendation to accept the proposed work.\n", "strength_and_weaknesses": "Strengths:\nThe main strength of the presented work is the combination of the clear presentation and the well grounded motivation for the proposed approach. Furthermore, the extensive experimental section clearly shows that the proposed relational attention mechanism accounts for the improved performance in the benchmark tasks.\n\nWeaknesses:\nThere are some minor formatting issues in the paper as of now.\nOn page 3, below equation 3, there seems to be a missing sentence or paragraph in front of the following section:\n[“… where Ni denotes the set of …”]\nThere is also a missing figure (or reference to a figure) on page 7, section 5.1.3:\n[“… when results are averaged over those classes (Figure ??).”\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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: Accept: notable-top-25%