Gated Relational Graph Attention Networks
Authors: Denis Lukovnikov
Asja Fischer
Venue:  (2021)
Keywords: graph neural networks
GNN
long-range dependencies
deep GNN
relational GNN

Abstract: Relational Graph Neural Networks (GNN) are a class of GNN that are capable of handling multi-relational graphs. Like all GNNs, they suffer from a drop in performance when training deeper networks, which may be caused by vanishing gradients, over-parameterization, and oversmoothing. Previous works have investigated methods that improve the training of deeper GNNs, which include normalization techniques and various types of skip connection within a node. However, learning long-range patterns in multi-relational graphs using GNNs remains an under-explored topic. In this work, we propose a novel GNN architecture based on the Graph Attention Network (GAT) that uses gated skip connections to improve long-range modeling between nodes and uses a more scalable vector-based approach for parameterizing relations. We perform an extensive experimental analysis on synthetic and real data, focusing explicitly on learning long-range patterns. The results indicate that the proposed method significantly outperforms several commonly used relational GNN variants when used in deeper configurations and stays competitive to existing architectures in a shallow setup.

Under review as a conference paper at ICLR 2021
GATED RELATIONAL GRAPH ATTENTION NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Relational Graph Neural Networks (GNN), like all GNNs, suffer from a drop performance when training deeper networks, which may be caused by vanish- ing gradients, wver-parameterivaaion,, and over-smoothing. Previous works have investigated methods that improve the training of deeper GNNs, which include nor- malization techniques and various types of skip connection within a node. However, learning long-range patterns in multi-relational graphs using GNNs remains an under-explored topic. In this work, we propose a novel relation-aware GNN archi- tecture based the Graph Attention Network that uses gated skip connections improve long-range modeling between nodes and uses more scalable vector-based approach for parameterizing relations. We perform extensive experimental analysis on synthetic and real data, focusing explicitly on learning rongeranee patterns. The proposed method significantly outperforms several commonly used GNN variants when used in deeper configurations and stays competitive to existing architectures in a shallow setup.
INTRODUCTION
In this work. we focus on learning long-range patterns in multi-relational graphs using graph neural networks (GNN), which heavily relies on the ability to train deep networky However, GNNs suffer from decreasing performance when the number of layers increased. /Zhoo & Akoglu (2020) point out that this may be due to (1) over-fitting, (2) vanishing gradients, and (3) over-smoothing (the phenomenon where node representations become less distinguishable from each other when more layers are used). Recently, several works have investigated over-fitting (Vashishth et al.] 2020)). over-smoothing (Li ct al. 2018: Chen et al. 2019 Zhao & Akoglu 2020 Rong et al. 20199 Yang et al. 2020), over-squashing (Alon & Yahav 2020). and possible vanishing gradient (Hochreiter &
Schmidhuber 1997: Pascanu et al. 2013 He et al. 2016) problems in GNNs (Li et al.) 2019a 2020
Rahimi et al. 2018).
One simple but effective technique to improve the training of deeper GNNs is using skip connections, for example, implemented by the Gated Recurrent Unit (GRU) (Cho et al.) in the Gated GNN (GGNN) (Li et al., 2015). Such connections can improve learning deep GNNs as it avoids vanishing gradients towards lower-layer representations of the same node, and reduces over-smoothing (Hamil- ton 2020 However, such vertical skip connections are not sufficient to enable learning long-range patterns. In addition, in relational GNNs, such as the Relational Graph Convolutional Network (RGCN) (Schlichtkrull et al., 2018), training difficulties may arise from the methods used for integrat- ing relation information, which may suffer from aver-parameterizatio and impact backpropagation.
In this work, we develop a novel GNN architecture for multi-relational graphs that reduces the vanishing gradient and over-parratttrizzatoonn problems that occur with existing methods and improves generalization when learning long-range patterns using deeper networks. Several changes are proposed to the Graph Attention Network (GAT) (Veličković et al., 2018), including a modified attention mechanism, an alternative GRU-based update function, and gated relation- aware message function. An extensive experimental study is conducted that (1) shows that different existing relation- aware GNNs fail learn simple patterns in simple synthetic sequence-based graph classification task, (2) presents a comparison and ablation study on synthetic node classification task, (3) shows that our architecture is competitive with existing ones an entity classification task using real-worke data from previous work.
We need least K GNN layers capture information that is K hops away.

---

Under review as a conference paper at ICLR 2021
2 BACKGROUND: GNNS AS MESSAGE PASSING NETWORKS
Many popular GNNs can be formulated within message passing (MP) framework (Gilmer et al. 2017). Consider mulli-relationns graph G = (V. where & consists of edges which are specified by triple (u, v, that define directed edge from u v, labeled by edge type (relation) r. A GNN maps each node E V onto representation vectors h h by repeatedly aggregating the representations of the immediate neighbours of every node and updating node representations in every step of the encoding process, cach associated with one of K layers of the GNN. Relational GNNs must also take into account the edge types between nodes in the graph G. In the following sections, we use the message passing framework where a single GNN layer/step is decomposed into a three-step process:
hg = ()) ( (e)nntttt)))))
where pd-) computes a "message" along a graph edge using the neighbour representation h h(-11) and the edge type of an edge from v. 7(-) aggregates the incoming messages into a single vector, and Φi-) computes a new representation for node v. E(, v) denotes the set of all edges in 9 that end in v. After subsequently applying Eq. [[ times to each node of the graph, the final node representations he (K) can be used for different tasks, such as graph or node classification. One commonly used message function is relation-specife linear transformation, which used by RGCNs and GGNNs: pMM(( r) = W, where W, is a DxD parameter matrix associated with edge type T. More-
over, GGNNs implement the update function 66.) using a GRU: !!t = GRU(h, (k-1) he 1)
()))a))))t)))))) the vector for the where the GRU's imput argument is b.(-11) = r r(fu(h ( aggregated neighbourhood of
MOTIVATION: BREADTH- BACKPROPAGATION
Many methods have very recently been proposed to mitigate vanishing gradients in GNNs, using tech- niques such residual connections (Li et al. 2019a 2020), "jumping knowledge" connections (Xul ett al. 2018) and DenseNets (Huang et al. 2017). which have effects similar to the Gated GNN from Li al. 2015). However, these techniques address only backpropagation in the depth of the network (i.c., vertically towards lower-level features of the same node). As we will now discuss, this not sufficient for learning long-range patterns since breadth-wise backpropagation (i.e., horizontally towards the neighbours) in such GNNs may still result in learning problems and vanishing gradients.
Consider a simple graph convolutional network (GCN) with the general update of the hidden units h* = o ((W(k) (h (k-1) + Eimnee h (1)) )), where a is a non-linearity such as a ReLU, Following the classical arguments, functions of this form will suffer from vanishing or explod- ing gradients because of the stacking of linear transformations (W) and non-linearities (ar). The backpropagation path from the top-level features (K) of a node to its initial features (0) is o (W(())(( ... (o(W )..))) With many layers (i.c., when K is large), the gradient magnitude diminishes at every step because of the multiplication with the derivative of the activation function, which is always for some choices. Additionally, depending on the values of the weights W, repeated multiplication with the weights may cause the gradients to either vanish or explode. This could become especially problematic when sharing weights between layers, which could be useful to combat pver-parameterizztion in deeper networks, which are necessary to encode multiple hops. These problems can be mitigated by the choice of activation function (such as using ReLU). using good initializations for the weights, and using normalization layers. LSTMs (Hochreiter & Schmidhuber] 1997). GRUs (Cho et al.), ResNets (He et al. 2016), Highway Networks (Srivastava et 2015). and DenseNets (Huang et al. 2017) propose an alternative solution by introducing some form of skip connection around one or more layers, such that every layer contributes an update additively. This ensures that the gradient to deeper layers does not vanish, and also that the gradient w.r.t. features (or states) in different layers (or timesteps) is similar (GRUs, Highway Network) or the same (ResNets). In fact, He et al. (2016) point out that the improvement they obtain is not due to gradient magnitudes and attribute the effect to the fact that modeling the residual error is an casier task for the network.
2

---

Under review as a conference paper at ICLR 2021
Depth-wise backpropagation for the simple GCN can be improved by adapting it to residual GCN (ResGCN) (Li et al. 2019a), such that we get the following update of the hidden units describing the node features: h [ he 1) + (( (h (k-1) + (u.))E ha ).. Alternatively, GGNN uses GRU-based update function that implements gated skip connection.
However, these techniques do not address breadth-win backpropagation (towards the neighhouring nodes), which is essential for learning long-range patterns. For illtustration of this problem, consider the hidden update of the ResGCN, We can easily see that every backpropagation path
from the top-level features he (K) of a node v to the (K - T.)-leel features h (K- of node that hops away is o (G(())(((-- (o (.. which contains L linear transformations and non-linearities. And all the backpropagation paths from h(K) to (()) also contain L such applications. A similar argument can be made for the GGNN, for which we provide a derivation of gradients in Appendix A.4
While proper initialization, the use of normalization layers, and non-saturating nonlinearities may maintain good gradient magnitudes, the training of the network can still be improved by implementing some form of breadth-wise skip connections. In addition, as we will experimentally confirm, the use of only depth-wise skip connections can actually hurt performance when the task requires learning patterns containing distant nodes.
Note that the breadth- wise gradient issues are further exacerbated when averaging aggregators used, which diminish the gradient towards a neighbour by a factor equal to the number of incoming edges. This leads to a gradient magnitude decay that is exponential in the distance between nodes. This drop is also related to the issues of oversmoothing and over-squashing (Alon & Yahav 2020).
4 GATED RELATIONAL GRAPH ATTENTION NETWORKS
In this section, we describe a novel class of GNN architectures that addresses the breadth-wise backpropagation issues and prevents exponential breadth- gradient decay. We propose several changes which all follow the general principle of using additive (gated) feature updates not only desth-wise (vertically) but also breadth-wisg (horizontally).
4.1 SYMMETRICALLY GATED RECURRENT UNIT
As claborated above, depth-wise residual update functions and GRUs as used in the GGNN improve depth-wise backpropagation towards lower-level features of the same node. To also improve the breadth-wind backpropagation, we propose to use an adapted version of the GRU. We call the proposed update function, which is described by the following equations, a Symmetrically Gated Recurrent Unit (SGRU):
h
(k-1) (k) =o D
Ur (r.h((t)) + brn))
r(h) = oWW, (K--1)
h + Ur. (k-1) + br.)
(2)
(k) We, h (k-1)
Uz h(:--)) + +bs.
2 (b) = Wa, n + Uza h(=-1)) + +bsn
(k-1)
(3)
2((+ We, T
(k-1)
U h bzn
200) (()) 2(k) = softmax( (K) (1) (0)
( ( 2,., -00)
(1=(0)
(4)
h (k) tanh( (W
2 (k)) + Uhh (k-1) o or(,) (R)))
(5)
(k)
1-11 1) (k)
+ h (k-1) + 2(4 e (())
(6)
h/
The SGRU differs from the GRU used in the GGNN in (i) introducing an additional reset gate rz that is applied to the aggregated neighbour states h (k-1) and (ii) computing the output state h. as a three-way mixture between the previous node state (k-1)) the aggregated neighbour states
h (k-1) and the candidate state (1) instead of two-way mixture between h (k-1) and (((h) The
interpolation coefficients 2 are produced by an elementwise softmax between the three z vectors. See also Figure for an illustration.
The vanilla GRU as applied to sequences has two inputs: the input vector 2, at a certain timestep and the state vector h. While it implements additive gated updates on h, it applies linear transformations
3

---

Under review as a conference paper at ICLR 2021
W
(011
A
8
WM
h (A)
(--)
Figure 2: The proposed SGRU update function.
Figure 1: The proposed gated message function.
and nonlinearities ø; before merging it into h. In the SGRU, both inputs are gated similarly, which lets the xy input benefit from the same additive gradient behavior as and gave rise to the name "symmetrically gated". This is crucial for improving horizontal information flow during the training of GNN since the 2; input of the SGRU receives the aggregated neighbourhood vector.
In synthetic task experiments (see Sections 5.1 and 5.2). we show that the SGRU is superior to the GRU as a GNN update function. However, this modification alone proved insufficient. To actually enable learning of long-range patterns, we also need to address the problem of exponential breadth- wise gradient decay and over-squashing (Alon & Yahav 2020). This is addressed by the modifications described in the following sections.
4.2 AYTENTION-BASER NEIGHBOURHOOD AGGREGATION
As elaborated at the end of Section 3 averaging aggregators, which are commonly used to stabilize GNN training, lead to decaying gradient magnitudes w.r.t. distant nodes. In addition, a simple, non-weighted sum based aggregator squashes the entire K K-hop receptive field of K K-layer GNN into a single vector uniformly, making it very challenging to distinguish features from the exponentially growing number of connected distant nodes (Alon & Yahav, 2020). For this reason, we believe that using an attention mechanism is crucial to enable the learning of long-range patterns in graphs. In the initial stages of training, when the attention weights are more uniform, the network might still suffer from exponentially decaying gradients. However, this problem should be reduced during training if attention learns focus on a few specific node.
To implement the aggregation function 7(-), we adapt the scaled multi head multiplicative attention mechanism (Vaswani et al.) 2017). The per-head attention distributions are computed as described for transformers, with two small but important differences: (1) the edge type embedding are used directly the keys when computing the attention, and (2) the linear transformations normally used to obtain value vectors are omitted. This last change follows the principle of using only additive operations to enable better long-range backpropagation through messages and node features. See Appendix A. for more detailed description.
4.3 USING EDGE FEATURES
Different ways of using edge features have been proposed. RGCN and GGNN use multiplication with relation-specific matrix (FMM). CompGCN (Vashishth al. 2020) and VR-GCN (Ye et al.) 2019) make use of vector-based relation parameterization, and explore composition functions inspired by graph embedding learning methods (Bordes et al. 2013 Yang et al. 2014 Nickel al., 2016). However, all these methods implement a linear transformation based update of the neighbour state.
To preserve the gradient in the message function, we must choose an additive function. simple possible choice is vector addition: MADD(h,, a,) = h, + a,- However, additive update functions of this form have the problem that under a non-weighted sum aggregator, the relation vectors are resolve
interchangeable. It is not clear whether simply using attention- aggregator this problem completely since (subsets of) the attention weights can be close to each other. This leads to the additional requirement of non-interchangeabbliy of relations: Va, b, c, d E R of с A b # > p(a, b) + p(c, d) # p(a, d) + p(c, b). The third requirement is vector- based parameterization of relation types to combat pveettrratttiinntioon in RGCN and GGNN.
We propose the following two-layer gated message function, which fulfills these requirements and model complex interactions between node and edge features (unlike some simpler choices that
4

---

Under review as a conference paper at ICLR 2021
1.=5
1,=10
1==15
I=5 (N=16)
RGCN
91.8
53,5
6.3 + 8.9
47.5 + 1.8
GGNN
69.7 + 3.3
2.5 1.8
3.3 2.4
80.1 + 1.4
RGAT
91.0 + 1.2
75.1 3.2
30.2 + 21.0
41.0 3.3
GR-GAT (SGRU)
98.6 + 1.0
93.2 2.7
95.9 + 4.2
SGRU
94.8 + 2.3
89.9 = 2.0
84.4
92.9 + 4.0
GRU
93.7 + 2.5
9.3
4.6 - 1.9
81.1 + 3.5
Table 1: Conditional recall results. The average accuracy on the set is reported. L. is the length of the generated sequences. The last column is a setting where the task length but a 16-layer network is used.
also fulfill the requirements for the message function).
z CELU(bA + (a(huaa,))
m mo=obb + W M²) O ha (1 m)
u= bn + Wnz
(GCM(hu
(8)
where a, is vector RP associated with the edge type from to u, and W A. W B. and Wm trainable weight matrices (which have their corresponding biases ba. bB and bm) that are shared between different edge types. See also Figure for illustration. CELU (Barron 2017) is used as the activation function. Similarly to highway networks (Srivastava et al. 2015), (GCM( implements a gate that interpolates (based on m) between the original node state h, and the relation-awars awarre update using a two-layer feedforward network. See also Appendix A.3
5 EXPERIMENTAL ANALYSIS
We wish to answer the following questions in our experiments:
Q.1 How well can the baselines learn simple rules for a sequence classification task? (5.1
Q.2 How does the proposed model compare to the baselines on a synthetic node classification task requiring long-range pattern learning? (5.2)
Q.3 Are all the proposed changes necessary to achieve the best performance? (..)
Q.4 How does the proposed method perform in a shallow setup on entity classification using real-world knowledge graph data? (5.3)
Q.5 Does the performance degrade on entity classification when deeper networks are used? (.3
The following baselines are used: (1) RGCN (Schlichtkrull et al. 2018), (2) GGNN (Li al. 2015
and (3) RGAT (Busbridge et al. 2019). We implement our RGCN and GGNN baselines based on code provided by the DGL framework. For GGNN, the parameters between layers are shared. We found several relational variants of the GAT in the literature (Busbridge et al.) 2019 Brockschmidt
2019 Sinha al. (201)) and chose adapt (Busbridge et al.) 2019) for the attention- baseline (RGAT). See Appendix A.2 for an elaborate description of the used RGAT and other details regarding memory-efficiency.
The following ablations of our method (GR-GAT) are considered in the experiments: (1) "GR-GAT (X), mean agg." replaces the attention based aggregation function with simple mean (equivalent to uniform attention). (2) "GR-GAT (X), edge-MM" replaces JGCM with μMM. and (3) "GR-GAT (X), val. transf." uses a linear layer to transform the value while using attention, like transformers. The X in GR-GAT(X) is the update function and can be one of the following: Ident (identity function), GRU (Gated Recurrent Unit), or SGRU (see Section 4. J). If X is omitted, the SGRU has been used. Weight are always shared between all layers of GR-GAT.
5.1 CONDITIONAL RECALL
In this experiment, we aim to answer Q.1 and show that the different popular relational GNNs are not able to solve simple sequence classification task that involves remembering one of the symbols in
5

---

Under review as a conference paper at ICLR 2021
1.00
GR-GAT
Accuracy
0.75
RGCN
GGNN.
0.50
0.25
175 200
8
next
next
nextt
Epoch
Figure 3: The imput graph (ovals) for an ex- ample of the Conditional Recall task and the computational graph for 3 GNN layers.
Figure 4: Training (dashed lines) and validation (full lines) accuracies per epoch for the best runs for different GNN types on the Conditional Recall task (1=15).
a sequence according to a set of simple rules. Here we deliberately choose the following setup to measure how well the different GNNs learn over larger numbers of hops in very simple graph.
We define sequence classification task where given a sequence of characters [xn] the model is asked to predict the correct class based the representation of the last node (corresponding to input Tx). The input sequences consist of strings of letters and digits of given length (which was varied between different experiments). The class of the sequence determined by the following rules: (i) if there is digit in the sequence, the first digit corresponds to the class label; (ii) otherwise, there an upper case character, the first upper case character is the class label; (iii) otherwise, the class is given by the first character in the sequence. Some examples are: "abcdefg" - "a", "abcDefg" - "D". "abed3Fg" > "3", "abCd3fg" - "3". Twenty examples were generated per output class for total of 1220 examples and the data was split in 80/10/10 train/valln satii//aalaaito//eee.. splits. For more details about the experimental setup for this task see Appendix|A..
The input sequences are transformed into graphs by (i) creating node for every character of the sequence and (ii) adding edges labeled using the next type between every adjacent element in the sequence. Given these edges, the GNN has to use at least N layers/steps in order propagate information from the first node to the last node. The number of layers is always set to + 1. The readout for prediction is done by taking the representation of the last node in the sequence.
5.1.1 RESULTS AND DISCUSSION:
The results for the different GNNs and varying sequence lengths (L) are shown in Table I (Note that all examples have the same, specified length in one experiment). While all baselines reach acceptable accuracy for length 5, their accuracy severely suffers when the length is increased. In contrast, our method solves the task well for all lengths. Figure4rreport the training behaviour in terms of training and validation set accuracies per epoch for the best runs of all considered GNNs, showing that the proposed GR-GAT model achieves much faster convergence and superior generalization this task when compared to the basclines.
Additional experiments are conducted directly compare SGRU and GRU. Here, the message function as well as the attention mechanism from GR-GAT were disabled, and self-edges were removed. The update function (SGRU GRU) receives the neighbourhood aggregating vector as the input and the lower-level features of node as the state. Clearly, the SGRU performs better, confirming our claims. Note that in this task, there only one real edge type and every node has at most one neighbour so the message and aggregation functions are unnecessary.
Surprisingly, the GGNN severely underperforms compared to the skip-less RGCN and RGAT. We suspect that, because of the gated skip connections to lower-layer node representations, it is easier for the GGNN to memorize combinations nearby nodes rather than learning meaningful patterns. Additional experiments are shown in the last column of Table [ The modified task follows the same rules but uses short sequences (L=5) and large number of layers (N=16). Even though many layers are used, the task thus requires looking over at most 4 hops in the graph. As we can see, the GGNN performs better than the other networks without depth-wise skip connections.
modified task were conducted to verify the GGNN, for which the results

---

Under review as a conference paper at ICLR 2021
It is important to keep in mind that the computational graph for GNN applied to this graph is different from an RNN applied to the same sequence. The "update distance" (the number of RNN or GNN updates performed) between the last state hr of an RNN and a token = (from k timesteps before) is k. In contrast, as illustrated in Figure 3 the update distance between the top-level features of any node and the initial features of any node is always equal to the number of layers in the GNN. In the figure, the final vector of the blue node is used for prediction and the red node specifies the desired output. Red arrows are "vertical" self-messages and blue arrows "horizontal" messages to neighbours. In the case of an RGCN, the neighbours and the node itself are treated equally, while the GGNN provides skip connection to previous node features, enabling easier backpropagation "vertically" within the node. However, this does not improve backpropagation to distant nodes in the graph (see also Appendix A.44).
We also inspected the gradients w.r.t. the input vectors and experimented with different initializations for the edge type matrices of the baselines. We found that the initialization indeed strongly affects the gradient magnitudes and affects training behaviour. However, even when the weights are initialized correctly and the initial gradients are not small, the baselines are still not able to solve the task well for larger task lengths. We believe that our proposed changes encourage more effective weight sharing across nodes and layers and may benefit from other effects that make it easier for the network to generalize. This is similar to the findings of He et al. (2016).
5.2
TREE MAX
In this experiment, we aim to answer Q.2 and Q.3 using a synthetic node classification task on trees. The input graphs are trees with nodes labeled with random integers between 1 and 100. The expected output labels for the node classification task are defined as the largest value of all the descendants of a node and the node itself. The graphs contain edges from a parent to its children, and from children to their parent, as well as self-edges. We use numbered child edges and child-of edges, for example, -CHILD-1-OF for the edge going from the first child of a node to its parent.
As an example of this task, consider the following input tree: (1 (2 ) (4 )) (5 (6 (7 (8) (9) I)). The nodes in the tree should be labeled with the value of their highest- valued descendant. Thus, the tree with its output labels will become: (10 (4 (3 (4) )) (I0 (6 (10 (8) ) (9 (10 }))). In this case, to correctly predict the output label of the root node (1), the GNN must handle three hops. Please see Figure in Appendix A.6 for illustration of the graph constructed for this example.
A total of 800 examples are generated, each containing one tree with a randomly chosen depth between 5 and 17. The largest generated trees contained more than 200 nodes. 17-layer GNNs (and fewer layers for the baselines) are used in the experiments. A 50/25/25% training/validationnnes split is used. Instead of training and evaluating with the expected labels of all nodes, we choose setting where the labels are omitted of node for which fewer hops must be resolved. Of the remaining nodes, only random 50% selection retain their labels. Unlabeled nodes are not used in loss or metric computation. More details about the data and the experimental setup can be found in Appendix A.7
5.2.1 RESULTS AND DISCUSSION:
As shown in Table 2 the best node-level and graph-leve accuraccess were obtained using the proposed GR-GAT model. Using the SGRU doesn't bring benefit compared to having no update function (Identity) in this task. A possible explanation is that the task is retrieval-oriented and can thus easily be solved using just the attention mechanism.
Concerning the claimed improvements of SGRU vs a normal GRU, we can see that GRU is the worst among the three tested options (SGRU, GRU or Identity) by a large margin. The ablation study further indicates that the gated edge function (Section 4.3) and adapted attention mechanism (Section 4.2 essential for achieving the best performance since the "edge-MM" and "val. transf." variants reach significantly worse performance.
Even though using no update function works well in this task, we believe the SGRU can be useful since it provides an alternative and more fine-grained mechanism for focusing on the previous node
'The graph-level accuracy is 100% for example only if all labeled nodes in the graph have been classified correctly, and is 0% otherwise
7

---

Under review as a conference paper at ICLR 2021
Node-level
Graph-level
RGCN
63.4 1.1
35.2 3.1
GGNN
21.0 + 2.4
7.7 2.5
RGAT
45.6 + 5.5
17.3 +
GR-GAT (SGRU)
93.0 + 0.9
82.5 +
GR-GAT (Ident)
93.1 + 0.5
83.0 0.7
GR-GAT (GRU)
33.3 23.5
20.4 23.2
GR-GAT (SGRU), mean agg.
72.0
GR-GAT (SGRU), edge-MM
90.3 0.3
77.0 0.8
GR-GAT (Ident), edge-MM
50.5 18.5
29.2 + 14.7
GR-GAT (Ident), val. transf.
83.1 + 3.2
65.3 + 4.3
Table Node and graph-level accuracies over the test set of the Tree Max task. Top part: baselines. Middle part: different update functions. Bottom part: other ablations. Note that the high variance for the ER-GAT (GRU) ablation is caused by one of the seven seeds resulting in much higher accuracy than the others.
RGCN
89.3
1.=2 (2 hops)
1,=10 (2 hops)
I==10 (subsample)
SynGCN
86.2 + 1.9
RGCN
95.8 (*)
88.0 = 1.3
89.8 - 6.9
WGCN
90.2 = 0.9
GGNN
94.4 + 2.2
92.6 + 1.3
95.4 + 2.6
CompGCN
90.6 + 0.2
GR-GAT
96.1 1.4
92.6 + 1.3
93.2 + 3.9
GR-GAT
89.7 + 0.6
(Ident)
96.3 1.3
92.6 + 2.6
96.3 + 1.3
Table 3: Accuracy on the test set of the AM dataset.
Table 4: Accuracy on test set of AIFB for different data settings (see text). (*) number taken from Schlichtkrull et al. (2018).
features (whereas the attention mechanism uses self-edge relation when attending to the previous node features and the granularity fixed to the number heads). This can also be seen in the ablation study, where the SGRU variant performs much better with the matrix multiplication based edge function PMM ("edge-MM" in the table) than the variant without an update function.
5.3 ENTITY CLASSIFICATION USING REAL-WORLD DATA
To answer Q.4 and Q.5, we run experiments on real-world data for the node classification tasks, where a certain property about an entity (which are nodes in the graph) must be predicted. is not clear whether this dataset could benefit from GNN that is able model longer patterns so we do not expect to see improvements using the original data. With these entity classification experiments, we mainly want to verify that our proposed model does not severly underperform compared to previously proposed relation-awer aawre GNNs in shallow setup and study the performance of our model when more layers are used.
The experimental setup is the same as in Schlichtkrull al. (2018). who use previously proposed datasets for entity classification in knowledge graphs. The same preprocessed datasets and train/test splits are used here. However, compared to Schlichtkrull al. (2018), who fit the entire dataset in memory, we implement subsampled mini-batch training. For more details, see Appendix [A.8] Experiments performed using two layers (similarly to Schlichtkrull et al. (2018). ), for which the results are reported in Table 3 for the AM dataset and in the first column of Table for the AIFB dataset. Further experiments are performed using the AIFB dataset to measure how much GR-GAT degrades when more layers are used, which is shown in the rest of Table 4
5.3.1 RESULTS AND DISCUSSION
The results in Tables B and the first column of Table show that our method is competitive with the previously proposed relation-awan GNNs in two-layer setup (L 2). The second column of Table that GR-Ga ERAT degrades less strongly than RGCN when ten layers (L = 10) are used on the same two-hop subgraph ("2 hops") ) as in the first column. The GGNN, which has vertical
8

---

Under review as a conference paper at ICLR 2021
coppeenneetinns and also shares parameters between layers, is similarly more resilient the increase in layer count. When a sampled subgraph is used that is built by random walks from the labeled node (which goes beyond two hops; also Appendix A.8). which is the setting reported in the last column of 4 we see some small improvement from all methods compared to a 10-layer network applied the two-hop subgraphs. However, there is still no improvement compared to the 2-layer GNN applied to a 2-hop subgraph. It is unclear whether the dataset could benefit from long-range pattern learning.
RELATED WORK
Li al. (2019a) investigate the GCN equivalents of ResNet (He et al., 2016) and DenseNet (Huang et al. 2017)) evaluated on point cloud semantic segmentation, as well as dilated aggregation. Residual- GCNs and Dense- GCNs (Li et al. 2019a). Highway GCN (Rahimi et al.] 2018). Column Net- works (Pham et al. 2017) and Li et al. (2020) are similar to the GGNN (Li et al. 2015) in using gated, residual or concatenated skip connections to previous nodes states. Xu et al.
(2018) propose
to add skip connections from all layers straight to the output layer to combat oversmoothing. The neighbourhood dilation proposed by [i et al. (2019a) for point cloud semantic segmentation increases the receptive field of the network without requiring the information to pass through other nodes. However, it is not clear how to apply this technique to multi-relationa. graphs. Additionally, different normalization techniques (Zhou al. 2020; Zhao & Akoglu [200 ei al.] (2020) have very recently been proposed that improve the training of deep GNNs. AGGCN (Guo et al. (2019) transforms a graph into fully connected graph and uses self-attention and thus, similarly to transformers (Vaswani et al., 2017), benefits from direct access to distant nodes. However, this leads to quadratic complexity the number of nodes (due to attention in fully connected graph). In contrast to previous work, we focus on improving the communication between neighbours in GNNs for multi-relational graphs.
A family of methods closely related GNNs are TreeLSTMs (Tai al., 2015) and GraphLSTMs (Peng et al., 2017 Liang et al., 2016 Song et al., 2018: Bresson & Laurent 2017).
Some versions of these methods have similar beneficial properties regarding backpropagation to distant nodes but are not suited for use in a general graph setup. [Song et al. (2018) adapt Graph L.TMs into a message passing network, however, their implementation of the L.STM-based update suffers from the same issues the GGNN. Compared to our proposed method, GraphLSTMs use independent forget gates for every neighbour instead of attention. [Song et al. (2018) uses a global forget gate, which reduces the ability of the model to focus certain nodes. The mixing gates in SGRU bear some similarity to those in the Sentence State LSTM (Zhang et al.] 2018). However, the original formulation of the Sentence State LSTM is not applicable for graphs in general. Fi-GNN (Li) et al. 2019b), similarly to a basic version of our work, uses a GGNN with attention based aggregation. However, lacks our modifications and investigation to improve long-range pattern learning.
CONCLUSION
In this work, proposed novel GNN architecture that can handle long-term dependencies in multi-relational graphs better than commonly used GNN architectures. Experiments on synthetic tasks show that popular GNNs are bad at learning long-range patterns, and are outperformed by the proposed method (GR-GAT) Real-world experiments show that our proposed method is at least competitive with previous Work.An ablation study indicates that the proposed changes w.r.t. the GAT and the GGNN are essential. The SGRU, which beats the GRU, is not absolutely necessary to have as the update function because the attention mechanism can mostly compensate for it while avoiding introducing additional parameters. However, we believe that the SGRU could still be useful as an orthogonal mechanism to control node representations and should be explored in applications. In future work, we plan to investigate additional model improvements and training techniques to further improve training of long-range relational GNNs.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.0522 2020.
Jonathan T Barron.
Continuously differentiable exponential linear units. arXiv, pp. arXiv-1704,
2017.
Antoine Bordes, Nicolas Usunier, Alberto Durai, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, pp. 2787-2795, 2013.
Xavier Bresson and Thomas Laurent. arXiv:171 2017.
Residual gated graph convnets.
arXiv preprint
Mare Brockschmidt. Gnn-film: Graph neural networks with feature-wist linear modulation. 2019.
Dan Busbridge, Dane Sherbur,, Pietro Cavallo, and Nils Hammerla. Relational graph attention networks. arXiv preprint arXiv: 1904.0581,
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. arXiv preprint arXiv:1909.032/1, 2019.
Kyunghyun Cho, Bart van Merriënboer Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares Holger Schwenk, and Yoshua Bengio. Learning phrase representations using mn incodrr-decoddd for statistical machine translation.
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 Kranning-Volume
Machine Learning- Volume 70, pp. 1263-1272. JMLR. org. 2017.
Zhijiang Guo, Yan Zhang, and Wei Lu. Attention guided graph convolutional networks for relation extraction. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguisties, pp. 241-251 Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/v 1/tp:////99911/1111 1024. UtLpttps: /www. wwwwww.wwwbb.c. wwtp///w....///atooooo/////t././ 1024
William I.. Hamilton. Graph representation learning (draft, september 2020). Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-159, 2020.
Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition. pp. 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEFE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015. httt:bttt///axtttt .rrg abs 141 4980
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE International Conference on Computer Vision, pp. 9267-9276. 2019a.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07739 2020.
Qimai Li, Zhichao Han, and Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirly-Seoond AAAI Conference Artificial Intelligence, 2018.
10

---

Under review as a conference paper at ICLR 2021
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks, arXiv preprint 1eXiv:5511.0544 2015.
Zekun Li, Zeyu Cui, Shu Wu, Xiaoyu Zhang, and Liang Wang. Fi-gnm: Modeling feature interactions via graph neural networks for etr prediction. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 539-548, 2019b.
Xiaodan Liang, Xiaohui Shen, Jiashi Feng, Liang Lin, and Shuicheng Yan. Semantic object parsing with graph LSTM. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling (eds.), Computer Vision ECCV 2016 - 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part I, volume 9905 of Lecture Notes in Computer Science, pp. 125-143 URL
Springer, 2016. doi: 10. 1110779778-3311-4444488 978-3-319-2 311-311-4444-48 46448-008
Maximilian Nickel, Lorenzo Rosasco, Tomaso A Poggio, al. Holographic embeddings of knowl- edge graphs. In AAAI, volume 2, pp. 3-2, 2016.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning. pp. 1310-1318, 2013.
Nanyun Peng, Hoifung Poon, Chris Quirk, Kristina Toutanova, and Wen-tau Yih. Cross-sentence n-ary relation extraction with graph Istms. Transactions of the Association for Computational Linguistics, 5:101-115, 2017.
Trang Pham, Truyen Tran, Dinh Phung, and Svetha Venkatesh. Column networks for collective classification. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 2495, 2017.
Afshin Rahimi, Trevor Cohn, and Timothy Baldwin. Semi-supervised user geolocation via graph convolutional networks. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers). pp. 2009-20133 2018.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations, 2019.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018
Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L Hamilton. Clutrr: diagnostic benchmark for inductive reasoning from text. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 4496-4505, 2019.
Linfeng Song, Yue Zhang, Zhiguo Wang, and Daniel Gildea. N-ary relation extraction using graph- state Istm. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2226 2235, 2018
Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. Highway networks. arXiv preprint ArXiv 2015.
Kai Sheng Tai, Richard Socher, and Christopher Manning. Improved semantic representations from tree-structured long short-term memory networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 1566, 2015.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- based multi- relational graph convolutional networks. In International Conference on Learning Representations, 2020. URL htRpsttss: wwt.//penrvvvveeee /ttepp/e//eeeeeeeeee..... n forum? 1B
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
11

---

Under review as a conference paper at ICLR 2021
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer G.
Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 4449-5458. PMIR, 2018. URL http: //proceedings m press v00 xu www.c.c...... BC. ht.ml
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint drXiv:1412.6575,22 2014.
Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting" over-smoothing" in deep gens. arXiv preprint arXiv:2003. 13663, 2020.
Rui Ye, Xin Li, Yujie Fang, Hongyu Zang, and Mingzhong Wang. A vectorized relational graph convolutional network for multi-relational network alignment. In Sarit Kraus (ed.). Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 4135-4141. ijcai.org. 2019, doi: 10. 00024993/iicai22211/574 URL
https: /dii...... owg/ 10 T1w.....2333... /ttp://l.........229///////aaaa. 2019///
Yue Zhang, Qi Liu, and Linfeng Song. Sentence-state Istm for text representation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp. 317-327, 2018.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020. URL
net/ forum?
Addrkeellrtw>
Kuangqi Zhou, Yanfei Dong, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Effective training strategies for deep graph neural networks, arXiv preprint arXiv:2006.07 1070070000000000 2020.
12

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 ATTENTION BASED AGGREGATOR
The query and key vectors for each attention head h (of in total H heads), (K) E RD for node and k E R for an edge e = (u, v, r) ending in U, respectively, are computed using head-specific linear transformations parameterized by Q (A)) E D/D and K(h) E D/
g.ah Q hb
k = ())h,,));
where [: denotes the (vertical) concatenation of two (column) vectors and a, is the same edge type-specific parameter vector that is used in Eqs. 7 Note that Eq. iss slightly different from standard attention mechanism, which would compute key vectors K khh,, We expect that including the edge type vector a, directly in the keys will make it easier to learn to place attention.
The attention score w (h) for an edge and head h is computed by a scaled dot product and then exp(w("")
normalized to obtain a (h) as usual: we (h) (h))) (a)) and oe Exrcer exp((
VD/H
Unlike multi-head attention in transformers and previous work (Veličković et al. 2018 Busbridge et al. 2019). we do not use linear transformations to obtain the value vectors. Instead, the vector (h,,r) r) Me |ue ..... ) is split in H equally sized chunks and the hi-th part fuc (h)
E R/H
taken as value vector for the f-th head. The attention scores (h and value vectors μee are then used compute the neighbourhood aggregation vector h for head h weighted sum. The full neighbourhood aggregation vector h, is then given concatenation over all heads l:
(h)
h
Σ
(1))) (1) p
h h 5... h (1)
(10)
(EE(..0
A.2 BASELINES
A.2.1 A NOTE ON MEMORY-EFFICIENG OF THE BASELINES
When experimenting with the baselines (RGCN, GGNN and RGAT), we quickly ran out of memory for larger hidden dimensions of the GNN and larger numbers of layers. This is caused by the relation matrices, which have Onn²) parameters for every relation. In the implementations relations were indexed from a tensor and have to be retained memory for every edge. While more memory-efficient implementations are possible, the existing ones sacrifice execution time, which can increase significantly with a large number different relations.
used, the
Gradient accumulation significantly slows down training. As simple fix to maintain reason- able training speed for our experiments, we replace (MM(-) in our RGCN and GGNN with jMM-rred (h,) Wo W.WW""' W,,,, where W is edge type specific square matrix of lower di- mensionality than W, and Wa and WB are matrices projecting into and out of WH's dimensionality that are shared for all edge types. Note that we did this only for the Tree Max experiments.
A.2.2 RGAT BASELINE
Like in (Busbridge et al. 2019), we use relation- speccfcc transformation matrices W and relation and head-specific query and key matrices (r.hh) and K(r
First, we define reletion-dependent representations for node, which is computed based on its current state (k-
w 2
(k-1)
(11)
Subsequently, for every head h, we define the Dolation-specifie query, key and value projections as:
(hr)) Q (h.r) (r)
gi
(12)
k (hrr) (birr) gi
(13)
(hrr) v(hir) (k-1)
(14)
13

---

Under review as a conference paper at ICLR 2021
We compute attention between messages M2, where indexes all edges in the input graph. First, we compute the attention score for message as (Vaswani et al. 2017)
(A) qi (h.r) (h.r)
(15)
where Mz is the message sent along an edge j + labeled by the relation r. Please note that node i may receive multiple messages from node j. and that those messages could contain the same relation.
The scores normalized over all messages that node i receives:
(h)
(16)
(K)
Ene
The normalized scores used to compute summary:
(h.k)
Evt
Z;
(17)
where r is the relation of fa and j is the source node id and is the target node id of message Pa. The updated representation for node i is then the concatenation over all heads, fed through the activation function a:
2 (k) a[z (0.k)
(H.
(18)
We experiment with a ReL.U, as well as with a linear a.
A.3 NOTES ON RELATION- MESSAGE FUNCTIONS.
Many different message function implementations are possible that take into account the relation connecting a node to neighbour. The default message function used in earlier literature is simply matrix multiplication:
PMM r) = W,h,,
(19)
This can easily lead to overparameterization and leads to difficulties implementing the GNNs in both memory-efficient and computationally efficient way.
In CompGCN, Vashishth et al. 2020) propose the following function:
PCompGoN (hw, r) Wx(r)(bu,,a>))
(20)
where W is one of the three matrices: one for forward relations, one for reverse and one for
self-edges, and @(h,, a,) ) a composition function that combines the neighbour state and relation vector. For the composition function, the authors explore functions inspired by knowledge graph embedding literature: subtraction (h,, a,), multiplication or cireular-correlation.
While this provides an alternative solution to wee-parraeteriiinn relations, and enables more efficient implementation, it does not improve gradient behavior since the backpropagation paths to the lower node features as well to distant nodes still contain linear transformation and gon-lincarities.
To improve backpropagation. we can make use of (gated or residual) skip connections. The residual version would have the following general form:
PRees (h,, r) (h,, h.
(21)
where la is some function. Similarly to transformers and ResNets, we choose to use two-layer MLP, which is more expressive than μMM, and unlike the composition-be babsed message functions in Vashishth et al. (2020). can effortlessly incorporate additional edge features that are not based on the relation embeddings.
We chose the gated skip connection described in the text over the simple residual one because enables better control of the additive contribution of the current layer and the residual version did not perform better in our early experiments. We leave a further investigation residuals to replace the gated skip connections for future work.
14

---

Under review as a conference paper at ICLR 2021
A.3.1 A NOTE ON INTERCHANGEABILITY OF RELATIONS
Note that the simple choice of adding relation vector, similarly CompGCN's subtraction version, might pose problems since it loses information about which relation was associated with which neighbour:
(h. + a,) + (hw +,)) (hw a,) + (h, + a,))
(22)
This is undesireable since it limits the expressive power of the network when using aggregator. is not clear to us how much this would affect models using attention- aggregation, however, we prefer avoid this since the attention-hase aggregator may behave like uniform sum, especially throughout the early stages of training.
This leads to the following condition that impose the message function: The message function must be chosen such that
pla, b) + p(c, d) & u(a d) + p(c,b)
(23)
iff a + e and + d. The gated message function JGCM proposed earlier in our work satisfies this condition.
A.4 BACKPROPAGATION TO DISTANT NODES IN GATED GRAPH NEURAL NETWORKS
The GGNN (Li et al. 2015 implements the update function 6(-) based on Gated Recurrent Units (GRUs) (Cho a
(2) o oW, (W, (k-1)
(k-1) + (* b,)
(24)
(4) a (W.h. (k-1)
+ h (k-1) 1) bz)
(25)
+ Uhh (k-1) @ (1)) 6(()) = tanh tanh (k-1) (h((k-1)
h
(26)
h h()) (1 z (1) c h! + z (0)
(27)
where (((-11) = ((
(k-1) (k-1)
(.))))))))) is the vector representing the aggregated neighbour-
hood of node
Consider a node classification task, where the top-level state ((K)) of node e is fed into a classifier
dC,
that produces a loss L.. To compute the gradient Vw dw where are the parameters of the model, we apply the chain rule as follows (here we ignore other nodes and only take into account only node v's contribution the gradient):
Oc, Ow
K Σ
Oc.
Th. (k)
V
VwC,
(28)
Th
(8)
Ow
k=0
with
Th (k)
II
(29)
th (k)
0h
(K)
Oh (k-1)
J k+
Oh (k)
Given the gated update equations of the GRU, the partial derivatives representation w.r.t. the previous node representation are:
of the updated node
(R-1)
0he (k)
0he
d(-z)
Oz
0h (k-1) (1 (1 0
h!
(k-
+
(k)
(30)
Oh.
(k-1 Oh
Oh
(k-
(k-1)
Th. (k)
The closer z is to zero vector, the closer the partial derivatives across layers
get the
0h (k-
identity matrix I and the more the following holds:
15

---

Under review as a conference paper at ICLR 2021
dc
(31)
Oh
(k)
Th. (K)
which has the effect that all the GGNN layers are skipped. practice, the gate will take on different values throughout training, but the additive update still allows to retain some contribution of the oh Th (K) deeper into the network.
original gradient
On the other hand, consider (K-1) (K-1)-layer GGNN applied a graph representing sequence length K. The sequence is represented as graph according to the same rules as described in Section [.1 the nodes are connected using only next-edges. Thus, only left-to-right propagation in the graph can be performed, and every node has only one incoming message, except the first, which has none. This is the setup that maximizes the ratio graph diameter per number nodes and edges.
When (K-l)-layer GGNN is applied to such a graph of K nodes, there is only one backpropagation
Oh K
(K)
path from node K to node
which is also the longest backpropagation path possible this
Ohg (0)
graph:
(K) Ohk K
Jh (k)
(32)
Ohp
(0)
(k-1)
Ignoring the used message function PMM and considering every node has only one neighbour, the
neighbourhood aggregation vector simply the neighbour node vector: h, (k-1) h k-1
(k-1)
Plugging this into the GGNN equations (Eqs. 24
gives:
tanhh [Wh (k-1)
0h
(33)
0h
0h (1-1)
k-
Oz
Otanh Otanh(Wh (Wh! (k-11)
tanh (t-1))
zz(N
(34)
0h (k-1)
0h (k-1)
do W. h (k-1))
(A) Otanh (Wan (k-1))
tanh(Wh (k-1)
(35)
0h
8h (x-1)
k-1
do W (k-1)
Both terms contain a partial derivative of the form
0h (k-1) which essentially identical to 8-1
the terms found in the backpropagation equations for vanilla RNN.
As in vanilla RNNs (without any gating like in GRUs and LSTMs), these terms can cause vanishing gradients due repeated multiplication with the derivative of o tanh nonlinearity and vanishing or exploding gradients depending on the values of W (which also change throughout training and thus could potentially reach unstable values).
In addition to the based argument outlined above, residual networks (as well as GRUs and LSTMs), benefit from better generalization abilities due to effects which were formalized or deeply studied in the literature known to us. Intuitively, the argument for residual networks (He et al. 2016) is that the individual residual blocks can easily learn to not contribute if necessary, which enables to learn very deep architectures, and otherwise, they only need to model the function that models the residual eиror computed from the output of the previous layer. addition, we believe that adding such skip connections enables more effective weight sharing across layers and nodes.
A.5 CONDITIONAL RECALL EXPERIMENTAL DETAILS:
In our experiments for this task, we randomly explore the following hyperparameter values for all compared methods: (1) dimensionality of node feature vectors in [150, 300] (larger values can cause
16

---

Under review as a conference paper at ICLR 2021
next
next
next
next
8
D
Figure 5: Example of imput graph for the Conditional Recall task. The top-level state the blue node used for prediction. The red node specifies the desired output.
memory issues with the basclines). (2) dropout in [0., 0.25, 0.5), (3) we set the dropout of embedding vectors to 0.1 (4) learning rate in [0.001, 0.0005, 0.0001]. For the baselines, we run for at least 200 epochs. For our GR-GAT, we reach high accuracy in 20 epochs and thus run only for maximum of 50 epochs. Throughout all of the experiments, we use the Adam (Kingma & Ba 2013) optimizer. We also use label smoothing with factor 0.1 everywhere. For our experiments with task length 15, we use the best hyperparameters found for length 10 for all methods and also experiment with smaller dropout values.
For the final reported accuracies, we trained with the best hyperparameters and loaded the model with the best validation error and evaluated on the test set. This was repeated with three different seeds that were shared between the tested methods.
The initial node states are initialized by embedding the node type using a low-dimensional embedding matrix (dimensionality 20; for vocabulary of 62 characters) and projecting the low -ow-dimesiional embeddings to the node state dimension using a learned transformation.
An example of graph used in this task is given in Figure 5 "8".
The output in this example should be
A.6
TREE MAX EXAMPLE
See Figure 6 on page 17
7
10
18
10
CHILD-1
5
-CHILD-1-OF
10
6
9
-CHILD-2 -CHILD-2-OF
6
9
1
-CHILLD --CHLLD---OF
10
4
4
8
4
8
CHILD-2
2
-CIIL-2-0F
4
3
3
Figure 6: Example of input graph for the Tree Max task. The double-ended arrow between node and node u represents two edges: one going from u to u and the other from u to v. Not every arrow labeled for clearer presentation. The labels the arrows indicate edge labels: the forward arrow -+ corresponds to the edge label for going from the parent to the child and <- for the reverse. The input labels are the black numbers and the output labels are the blue numbers. Note that we use semi-supervised version of this task, where we erase the output labels of a large portion of the nodes, ie. ignore their output labels in training and testing.
A.7 TREE MAX EXPERIMENTAL DETAILS:
During data generation, we first randomly pick a tree depth between five and fifteen. Then, we generate tree, choosing between 0, 2 children for each node until reach the chosen tree depth. The largest trees in our generated data contained over 200 nodes. The generated dataset contained 800 examples; we used 50/25/25 train/validation/eest split.
17

---

Under review as a conference paper at ICLR 2021
Not every node in the dataset is annotated. For every example, which consists of one graph, the nodes which are at most 2 away from their "answer" node (which contains their output label) are ignored (not used in training testing). Of the remaining nodes, which require to propagate information for at least 2/2 to be solved, only 50% is retained for training and testing. Here, N is the maximum depth of the tree. This setup defines a semi- supervised node classification setup. The reason for using the semi- semi-supereieed version instead of the previous version, which was fully supervised is that the task can be solved iteratively using immediate neighbour states only. Because of this, all methods reached very high node classification accuracy. In the semi-supervised version, the models have to learn what information to retain in unlabeled nodes, which are in between labeled nodes and their corresponding "answer" nodes.
For every model tested, we perform a hyperparameter search using all predefined seeds. For all models, we experiment only with dimensionality of 150 to avoid memory issues and ensure fair comparison regarding representation dimensionality. Then we run the best hyperparameter setting with three different random seeds and report the test results in Table 2 Note that the same seeds are re-used for experiments for all models, and that every seed results in a different dataset being generated. We used early stopping and reloaded the best model based element- wise accuracy on the validation set. Patience was set to 10 epochs but every experiment was run for a minimum of 50 epochs.
The models were evaluated using node-wise and graph-wise accuracy. The graph-level accuracy is 100% for example only if all gold-labeled nodes in the graph have been classified correctly, and is 0% otherwise.
In our experiments, we randomly explore different combinations of different hyperparameter settings: dropout is selected from {0., 00,, 0.25, 0.5), dimensionality of node vectors is fixed to 150 for all methods. Learning rate chosen from {0.001, 0.000333, 0.0001]. For all baselines, the number of layers was chosen from 10, 17. Note however that 10 layers is insufficient to perfectly solve the task.
A.8 ENTITY CLASSIFICATION EXPERIMENTAL DETAILS
We use the datasets as provided at bttts::/ moving some code for more memory efficient storage. The datasets contain graphs, where only fraction of nodes carries a label that we should predict (we call these nodes labeled nodes). We train on the train portion as provided on the repository and test on the predefined test portion.
re-
During experiments, we train with two different settings: (1) a fixed two-hop (subsampled) subgraph and (2) a fixed subsampled random walk subgraph.
In the first setting (two-hop subgraph), we retrieve for every labeled node that will be classified a two-hop, at most 6000 nodes (and 10000 edges) subgraph. During batching, these subgraphs are merged. Note that the number of nodes (or edges) exceeds the maximum number of nodes (6000), we stop expanding. We experiments with the following hyperparameter ranges; (1) dropout from 0.25, 0.5, (2) embedding dropout from 0.25, 0.5, (3) dimension from 64, 96, (4) learning rate from 0.005, 0.001, 0.00025. We use at least 50 epochs and early stopping with patience set 10 epochs to terminate validation runs earlier and save computation time. The number of heads in our GR-GAT method set four for all tried dimensions. During hyperparameter search, we run random selection of all possible combinations with three different seeds, using a subset of the training set (80%) for training and another set (20%) for validation. After determining the best hyperparameters, we use them to train a final model on the entire training set and evaluate on the test set. The reported numbers use three different seeds.
In the second setting (random walk subgraph), we use random walks to generate the subgraph. For every labeled node, we precompute a subgraph of most 2000 nodes and 3000 edges, using 5% reset probability in the random walk. During batching, these subgraphs are merged. Note that the subgraphs are precomputed once before training and fixed throughout, so the subgraphs do not get resampled at every epoch. We use the same set of seeds for the different methods we test to ensure that the methods have been tested on the same sets of data. We experiments with the following hyperparameter ranges: (1) dropout from 0., 0. 0.25, 0.5, (2) embedding dropout from 0., 0.1, 0.25, (3) dimension from 32, 64, (4) learning rate from 0.01, 0.005, 0.001, 0.00025. We use at least 50 epochs and early stopping with patience set 10 epochs to terminate validation runs earlier and save
18

---

Under review as a conference paper at ICLR 2021
computation time. The number of heads in our GR-GAT method is set 4 for all tried dimensions. Since GR-GAT (Ident) reached near 100% training accuracy with the chosen hyperparameters after 15 epochs, we ran it for 20 epochs during final tests. During hyperparameter search, we randomly run all possible combinations with three different seeds, using a subset of the training set (80%) for training and another set (20%) for validation. After determining the best hyperparameters, them to train final model on the entire training set and evaluate on the test set.
In both settings, we erase the initial features (embeddings) of the nodes for which make predictions by setting them to the same learnable vector that is reused everywhere.
19


Reviews:
[{"review_id": "RTLVgcUQL3i", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 2, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThis paper presents a graph attention architecture that captures long-range interactions. The novelties in the architectures are (1) vector-based parameterization of edge type in modeling message, (2) slight modification of graph attention (Section 3.2), and (3) GRU-based node update function. The experiments are primarily on synthetic tasks. However, it is unclear if modeling such long-range interaction is useful in real tasks. The paper fails to demonstrate convincing results on the real tasks of entity classification in knowledge graphs.\n\n## Pros\n1. Detailed architecture explanation.\n2. Good performance on synthetic tasks.\n3. Careful design of synthetic tasks.\n\n## Cons:\n1. The novelty of architecture is limited as detailed below.\n- Vector-based parameterization of edge type in the relational graph has been commonly adopted in GNNs for molecular graphs (e.g., Eq (1) in https://arxiv.org/pdf/1709.04555.pdf), and not novel. \n- The modifications of graph attention architecture are rather minor (removing a single linear transformation, adding edge type embedding in the key of the attention mechanism). \n- GRU-based node update function is not empirically shown to be beneficial although being highly complicated.\n2. Experiments are largely synthetic, and no convincing results are provided for the real datasets on entity classification in knowledge graphs. It is unclear if modeling long-range interaction is useful in practice. One domain long-range interaction could be useful is molecule classification, where you can treat molecular graphs as multi-relational graphs and those graphs tend to have large graph diameters. Many datasets are readily available [here](https://ogb.stanford.edu/docs/graphprop/).\n3. Details of the real knowledge graph datasets (AIFB and AM) are not provided in the main texts.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MQC1SF8RmJp", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose Gated Relational Graph Attention Nets (GR-GAT), a set of modifications to the GAT architecture in order to make them stronger under long-range relational reasoning, evaluating on various hand-crafted benchmarks as well as a real-world dataset previously explored in the area.\n\nThe GR-GAT tackles all aspects of the graph neural network pipeline:\n- Message function that takes into account the edge type embedding, and features explicit gating over the sender node's past features, and usage of the CELU activation;\n- Multi-head attentional aggregator which splits the value vectors into chunks, rather than replicating them;\n- Symmetric approach to the GRU update rule, which factors both inputs into the gating.\n\nThe three approaches are potentially meaningful for ameliorating various issues with long-range reasoning, such as overfitting or vanishing gradients, and I think the methodology from this paper could be useful to GNN practitioners. However, the paper's current presentation and motivation does not feel suitable for a venue like ICLR, in my opinion.\n\nMy main concern is that the authors do not properly motivate most of their design choices, or properly ground them in a particular issue with (R)GATs or GGNNs. Many choices (to name a few: the gating message, the CELU activation, or the splitting value vector) are name-dropped in the paper, without properly explaining their significance in the architecture. The ablation studies and experimental discussions are also lackluster in this sense, in my opinion: the authors' discussion doesn't go much further than \"the results demonstrate method X outperforms method Y\", not managing to provide deeper insight into any of the design choices.\n\nThe best-motivated addition---the SGRU update---is in my opinion a pretty neat idea and should be more highlighted and motivated in the paper, perhaps with experiments specially designed to show its benefits. Gated attention as well as split messages have already been featured or attempted (in some form) by prior work: see, for example, the GaAN model from Zhang et al. (UAI 2018), hence the novelty of such proposals, in isolation, is limited.\n\nWhile the GR-GAT model achieves some strong outcomes on synthetic benchmarks, the strength of these results is, in my opinion, insufficient to carry the weight of the paper, especially for a venue like ICLR. Especially considering that these graphs are designed with rather simple edge types (such as edge direction), the value of these results when transferred to real-world heterogeneous graphs is unclear. Further, the max-tree benchmark, where most of the interesting ablations are shown, is a bit concerning: it appears as if it could be quite easy to solve if using max-aggregation rather than attention (see Richter and Wattenhofer's \"Normalized Attention Without Probability Cage\" for some motivation on this), and maybe in this sense would not require any of the \"heavy artillery\" proposed here. \n\nAs mentioned above, it would be interesting to create more targeted and diverse synthetic benchmarks, perhaps to specifically battle-test the SGRU component.\n\n========= Post-rebuttal update:\nI thank the authors for carefully addressing my comments, as well as other reviewers'.\n\nUltimately, this is a nice paper with a novel recurrent component, and I can see how it could perform well in practice.\nHowever, the lack of stronger real-world experimentation (on datasets such as OGB) unfortunately renders the contribution insufficient -- the synthetic benchmarks being insufficient on their own to pull the weight of the paper.\n\nI retain my score, but encourage the authors to carefully revise and resubmit for the next venue should the paper be rejected.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JEBS70p279y", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary:\n\n    The authors propose a new gating based recurrent graph attention networks for multi-relational graphs to capture long-range neighbor dependencies. The authors provide an interesting analysis of current gated GNN models (in the appendix + Figure 3) in light of their ability to capture long-range dependencies in graphs. Experimental results are reported for node classification with two synthetic datasets and two real-world datasets.  \n\n——\n\nPros:\n\n\t(i) The work addresses an important problem of long-range dependencies with conventional graph neural networks. The work has an interesting backpropagation based explanation of the issue in the Appendix and Figure 3 provides a good illustration of the same. \n\t(ii) The synthetic experiments are interesting and helpful to evaluate models for long-range dependencies \n\t(iii) Impressive results on synthetic experiments \n\t\n——\nMajor Concerns:\n\n\t(i) Though the problem of interest is explained well in the appendix from the view of Gated GNNs. The paper's main section lacks a clear explanation of the problem; especially, there is no explanation of what it means by the horizontal vanishing gradient problem. \n\n\t(ii) The model motivation is not clearly written in the main paper — why model both the inputs as states of a gated recurrent network. Eqn: 10 is not straightforwardly clear why the redundant combination of information is helpful. Overall, the primary contribution discussed in section 3.3.1 needs to be expanded and explained in contrast to GRU update to capture long-distant neighbor information. A similar backpropagation analysis for the proposed model will help us understand the power of the proposed model. Also, why is the model called 'symmetrically' GRU? \n\n\t(iii) The r_x gate in Eqn: 9 is similar to the forget gates in LSTMs. How does it compare with the GraphLSTM updates? \n\n\t(iv) Residual and Dense connections are not discussed and experimented. Like in JK-Nets, dense connections can be added to the each of the GCNs pertaining to different relations or can be added for the combined layer output from all relations. The baselines with highway connections need to be evaluated. \n\n\t(v) There are too many components or design choices proposed/made, but there are no ablation studies on all the components. (a) Gated relational message, (b)Redundant usage of relational information for attention keys, (c) Concat-Ensemble of value vectors (d) symmetric GRU. Even in the current set of variations, would like to see, GR-GAT(SGRU) - value transformation, GR-GAT(SGRU) \n\n\n\t(vi) Results are reported only for two real-world datasets. MUTAG and BGS can be added. No real-world datasets or tasks with potential long-range dependencies are experimented. Ex: Molecular graphs (MUTAG, ZINC, etc. ) and Protein graphs.\n\n\t(vii) Tree Max:\n\t\t- A height wise results+analysis of node-level task would be interesting.\n\t\tIt is especially hard to understand why the GR-GAT(Ident)- value transform performs poorly. On the same note, how does GR-GAT(SGRU) - value transformation perform?\n\t\t- Why does GR-GAT(GRU) perform way poorer than GR-GAT(Ident) ? \n\t\t- The text about model variations mentions GATE and SGRU to be the same but in Table: 2, there is both GR-GAT (SGRU) and GR-GAT(Gate). \n\t\n\t(viii) WGCN results on AIFB ?\n\n\t(ix) Only node classification results reported, in which case the scope of the model and results studied should be explicitly mentioned to be restricted to node classification if that is the intent. If that is not the case, additional link prediction results like RGCN or other tasks should be reported. \n\n\t\tAlso, Additional results on single-relational homogeneous graphs can help disentangle the effect of the proposed relational module from the main contribution, the gating mechanism.\n\t\n\nOverall Recommendation:\n\n       The paper has interesting content, but the paper is not well organized and motivated well. There is sufficient merit if the analysis could be reformulated and generalized for all message-passing models — the horizontal long-term dependency. The backpropagation based vanishing gradient issue discussed is limited to Gated GNNs alone. It is essential to discuss residual and dense connections too. On the experimental front, adding more real-world datasets would strengthen the paper. \n——\nPost Rebuttal \nIncreased the score from 6 to 7. \nI would have strongly recommended the paper if it had more real-world datasets. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "El5akkWU2Ma", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#####Summary#####\n\nThis paper proposes a new GNN model (GR-GAT) for multi-relational graphs. The proposed method has better ability of capturing the long-range information. Essentially, the proposed GR-GAT is modified from GAT so that it can apply to the multi-relational graphs. Since the modifications are common and frequently used techniques, the novelty of this work is not enough. Also, why these modifications can help to capture long-range information is not well explained in this paper. Overall, this work is ok but not good enough for ICLR.\n\n#####Pros#####\n\n(1) The experiments on synthetic are well designed and can show the power of the proposed GR-GAT. \n\n(2) This paper studies a meaningful and challenging problem; that is capturing long-range information using GNNs.\n\n#####Cons#####\n\n(1) The novelty of the proposed method is not enough. Based on the description in Section 3, the proposed model is basically under the message passing framework (Eq (1)) and the concrete implementations of the three functions included in the message passing framework is not novel. For example, parameterizing message function using vector, aggregating neighborhood using attention, and updating using GRU are all popular used techniques in GNNs. Overall, this method is likely to be a combination of GAT and some basic techniques for multi-relational graphs.\n\n(2) More importantly, the motivation is not explained clearly. The current version did not well explain why the proposed model can help to model long-range dependencies in Section 3. \n\n(3)  To show the ability of capturing long-range dependencies, the experiments are only conducted on small synthetic datasets and specific defined tasks. It is not enough to show the ability of capturing long-range information. More experiments and comparisons on large real-world datasets should be considered.\n\n#####Suggestions for improvement#####\n\n(1)\tI think the main issue of the current version is that our readers cannot tell the contributions of this paper from Section 3. We cannot find what is the key proposal of this paper and how this proposal can help to capture long-range information. I think if this point can be improved, the novelty and motivation of this paper can be clearer.\n\n\n######\n\nUpdate: After looking at the revised version, I would like to raise my score to 5 since the motivation is clearer.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a GNN architecture for multi-relational data to better address long-range dependencies in graphs. The proposed GR-GAT model is a variant of graph attention networks (GAT) with, among other modifications, vector-based edge type embeddings and GRU-type updates. Results are presented on AIFB, AM, and on synthetic benchmarks.

The reviewers agreed that this is an interesting contribution and that the results on the chosen synthetic benchmarks are insightful, but that experimental evaluation on real data and overall motivation of the architecture is lacking. In the rebuttal period, the authors have improved the writing and strengthened the motivation of the paper. However, given the limited amount of time, the authors were not able to sufficiently address the lack of experimental validation on real data (beyond AIFB & AM). I am inclined to agree with the reviewers that this paper needs significantly more work on the experimental evaluation, the overall presentation needs to be refined and it needs to more carefully analyse the effect of each individual architectural modification to meet the bar for acceptance.

Decision: Reject